Rank-Independent Spectral Hypergraph Sparsification via Global-Dictionary Chaining
arXiv:2607.09074
The paper proposes a method to create a spectral ε‑sparsifier for any weighted hypergraph using only O(n log n / ε²) hyperedges, eliminating the dependence on the hypergraph’s rank by introducing a global‑dictionary chaining technique.
Abstract
We show that every weighted hypergraph on vertices admits a spectral -sparsifier with 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.
The paper is withdrawn because the cited result does not support Theorem 3, invalidating the subsequent argument