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 ε−2 logn logr) hyperedges in nearly-linear 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(minn ε−4 log3 n,nr3 ε−2 logn) and runtime was O(mr + nO(1)).