The thesis provides near-optimal streaming ellipsoidal rounding algorithms, block Lewis weight sparsification, dueling optimization with monotone adversaries, PAC analysis of backdoors, and spectral clustering robustness, all with detailed proofs.
Spectral hypergraph sparsification via chaining
1 Pith paper cite this work. Polarity classification is still indexing.
1
Pith paper citing it
abstract
In a hypergraph on $n$ vertices where $D$ is the maximum size of a hyperedge, there is a weighted hypergraph spectral $\varepsilon$-sparsifier with at most $O(\varepsilon^{-2} \log(D) \cdot n \log n)$ hyperedges. This improves over the bound of Kapralov, Krauthgamer, Tardos and Yoshida (2021) who achieve $O(\varepsilon^{-4} n (\log n)^3)$, as well as the bound $O(\varepsilon^{-2} D^3 n \log n)$ obtained by Bansal, Svensson, and Trevisan (2019). The same sparsification result was obtained independently by Jambulapati, Liu, and Sidford (2022).
fields
math.OC 1years
2025 1verdicts
CONDITIONAL 1representative citing papers
citing papers explorer
-
A Geometric Approach to Problems in Optimization and Data Science
The thesis provides near-optimal streaming ellipsoidal rounding algorithms, block Lewis weight sparsification, dueling optimization with monotone adversaries, PAC analysis of backdoors, and spectral clustering robustness, all with detailed proofs.