Rank-Independent Spectral Hypergraph Sparsification via Global-Dictionary Chaining

Abstract

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 2023 works of Lee and Jambulapati--Liu--Sidford by removing their rank dependence and answering Lee's open question on whether this loss is inherent. The key idea is global-dictionary chaining: after choosing clique edge weights with balanced effective resistances, every hyperedge seminorm is Lipschitz with respect to the same global-dictionary norm generated by normalized vertex-pair directions; the local rank complexity is thereby replaced by the Gaussian width of this common dictionary. Since these STOC 2023 works have become standard analytic primitives across a broad subsequent literature on spectral hypergraph sparsification and its variants, our rank-independent theorem sharpens many later guarantees that inherit their sampling bounds.

arXiv commentThe paper is withdrawn because the cited result does not support Theorem 3, invalidating the subsequent argument