Spectral Hypergraph Sparsification via Chaining

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

Authors

• James R. Lee

Keywords

• Hypergraph sparsification
• chaining
• independent random sampling
• subgaussian processes