{"ID":6497841,"CreatedAt":"2026-07-13T01:19:40.13847098Z","UpdatedAt":"2026-07-14T01:36:59.12045529Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2607.09074","arxiv_id":"2607.09074","title":"Rank-Independent Spectral Hypergraph Sparsification via Global-Dictionary Chaining","abstract":"We show that every weighted hypergraph on $n$ vertices admits a spectral $\\varepsilon$-sparsifier with $O(n\\log n/\\varepsilon^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.","short_abstract":"We show that every weighted hypergraph on $n$ vertices admits a spectral $\\varepsilon$-sparsifier with $O(n\\log n/\\varepsilon^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 inh...","url_abs":"https://arxiv.org/abs/2607.09074","url_pdf":"https://arxiv.org/pdf/2607.09074v1","authors":"[\"Chenghua Liu\",\"Yuxin Zhang\"]","published":"2026-07-10T03:39:06Z","proceeding":"cs.DS","tasks":"[\"cs.DS\"]","methods":"[]","has_code":false}