Spectral hypergraph sparsification via chaining

Abstract

In a hypergraph on $n$ vertices where $D$ is the maximum size of a hyperedge, there is a weighted hypergraph spectral $\epsilon$-sparsifier with at most $O({\epsilon }^{-2}\log (D)\cdot n\log n)$ hyperedges. This improves over the bound of Kapralov, Krauthgamer, Tardos and Yoshida (2021) who achieve $O({\epsilon }^{-4}n(\log n{)}^3)$, as well as the bound $O({\epsilon }^{-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).

Incorrect example replaced by Remark 1.2; Definition of the distance corrected; reference to JLS'22 added