Proves existence of dimension-independent Euclidean Steiner (1+ε, O(√(1/ε)))-shallow-light trees for arbitrary finite point sets and roots in R^d.
A unified framework for light spanners
7 Pith papers cite this work. Polarity classification is still indexing.
7
Pith papers citing it
citation-role summary
background 1
method 1
citation-polarity summary
verdicts
UNVERDICTED 7representative citing papers
Introduces a rank measure for FO logic and proves a rank-preserving Gaifman normal form, yielding a simplified proof for almost-linear time decision of FO properties on nowhere-dense structures.
First approximate calibration results for discrete properties in multiclass settings via Lipschitz intermediaries for strongly orderable discrete properties.
Introduces SCDL as a calibration measure that is fully actionable for full swap regret and testable with nearly optimal sample error while satisfying continuity and consistency.
Any low-success-probability LPN solver can be transformed into a high-success-probability solver on scaled parameters LPN with noise and dimension divided by k = Θ(1/δ log 1/ε).
First efficient sum-of-squares algorithms recover exact and approximate overlapping planted cliques in dense random intersection graphs for k ≫ √(n log n), with robustness to noise, monotone adversaries, and optimal edge corruptions.
Model checking for low-monodimensionality fragments of CMSO with disjoint-paths predicate is FPT on topological-minor-free graph classes.
citing papers explorer
-
Euclidean Steiner Shallow-Light Trees in Higher Dimensions
Proves existence of dimension-independent Euclidean Steiner (1+ε, O(√(1/ε)))-shallow-light trees for arbitrary finite point sets and roots in R^d.
-
A Rank-Preserving Gaifman Normal Form
Introduces a rank measure for FO logic and proves a rank-preserving Gaifman normal form, yielding a simplified proof for almost-linear time decision of FO properties on nowhere-dense structures.
-
Smoothed Elicitation Complexity for Approximate $\Gamma$-calibration of Discrete Classification Tasks
First approximate calibration results for discrete properties in multiclass settings via Lipschitz intermediaries for strongly orderable discrete properties.
-
Testable and Actionable Calibration for Full Swap Regret
Introduces SCDL as a calibration measure that is fully actionable for full swap regret and testable with nearly optimal sample error while satisfying continuity and consistency.
-
Hardness Amplification for (Sparse) LPN
Any low-success-probability LPN solver can be transformed into a high-success-probability solver on scaled parameters LPN with noise and dimension divided by k = Θ(1/δ log 1/ε).
-
Robust Algorithms for Finding Cliques in Random Intersection Graphs via Sum-of-Squares
First efficient sum-of-squares algorithms recover exact and approximate overlapping planted cliques in dense random intersection graphs for k ≫ √(n log n), with robustness to noise, monotone adversaries, and optimal edge corruptions.
-
Model Checking for Low Monodimensionality Fragments of CMSO on Topological-Minor-Free Graph Classes
Model checking for low-monodimensionality fragments of CMSO with disjoint-paths predicate is FPT on topological-minor-free graph classes.