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

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.