# Chaining, Group Leverage Score Overestimates, and Fast Spectral Hypergraph Sparsification

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

## Key facts

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

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

- [Nearly Tight Regret Bounds for Profit Maximization in Bilateral Trade](https://mlsanity.com/paper/2509.22563/) (2025)
- [Ridge Leverage Score Sampling for ℓp Subspace Approximation](https://mlsanity.com/paper/2407.03262/) (2024)
- [Sparsifying Suprema of Gaussian Processes](https://mlsanity.com/paper/2411.14664/) (2024)

## Abstract (arXiv)

We present an algorithm that given any n-vertex, m-edge, rank r hypergraph constructs a spectral sparsifier with O(n varepsilon-2 log n log r) hyperedges in nearly-linear widetildeO(mr) time. This improves in both size and efficiency over a line of work (Bansal-Svensson-Trevisan 2019, Kapralov-Krauthgamer-Tardos-Yoshida 2021) for which the previous best size was O(minn varepsilon-4 log3 n,nr3 varepsilon-2 log n) and runtime was widetildeO(mr + nO(1)). Independent Result: In an independent work, Lee (Lee 2022) also shows how to compute a spectral hypergraph sparsifier with O(n varepsilon-2 log n log r) hyperedges.