# Spectral hypergraph sparsification via chaining

arXiv: https://arxiv.org/abs/2209.04539 · HTML: https://mlsanity.com/paper/2209.04539/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 9 Sep 2022.

## Built on by (most cited first, 2 of 2)

- [On Approximability of ℓ22 Min-Sum Clustering](https://mlsanity.com/paper/2412.03332/) (2024)
- [Sparsifying Suprema of Gaussian Processes](https://mlsanity.com/paper/2411.14664/) (2024)

## Abstract (arXiv)

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) · 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 D3 n log n) obtained by Bansal, Svensson, and Trevisan (2019). The same sparsification result was obtained independently by Jambulapati, Liu, and Sidford (2022).