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

Abstract

We present an algorithm that given any $n$-vertex, $m$-edge, rank $r$ hypergraph constructs a spectral sparsifier with $O(n{\epsilon }^{-2}\log n\log r)$ hyperedges in nearly-linear $\tilde{O}(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(\min \{n{\epsilon }^{-4}{\log }^{3}n,n{r}^3{\epsilon }^{-2}\log n\})$ and runtime was $\tilde{O}(mr+n^{O(1)})$. Independent Result: In an independent work, Lee (Lee 2022) also shows how to compute a spectral hypergraph sparsifier with $O(n{\epsilon }^{-2}\log n\log r)$ hyperedges.