Rank-Independent Spectral Hypergraph Sparsification via Global-Dictionary Chaining

Chenghua Liu, Yuxin Zhang

We show that every weighted hypergraph on $n$ vertices admits a spectral $\epsilon$-sparsifier with $O(n\log n/{\epsilon }^2)$ hyperedges, strengthening the independent STOC 202…