Spectral hypergraph sparsification via chaining

DOI10.1145/3564246.3585165MaRDI QIDQ6410246zbMATH OpenFDO

Authors James R. Lee

Publication date 9 September 2022

Full work available at URL https://doi.org/10.1145/3564246.3585165

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Abstract: In a hypergraph on $n$ vertices where $D$ is the maximum size of a hyperedge, there is a weighted hypergraph spectral $varepsilon$-sparsifier with at most $O(varepsilo{n}^{-2}log(D)cdotnlogn)$ hyperedges. This improves over the bound of Kapralov, Krauthgamer, Tardos and Yoshida (2021) who achieve $O(varepsilo{n}^{-4}n(logn{)}^3)$, as well as the bound $O(varepsilo{n}^{-2}{D}^{3}nlogn)$ obtained by Bansal, Svensson, and Trevisan (2019). The same sparsification result was obtained independently by Jambulapati, Liu, and Sidford (2022).

Cited in

(9)

• Splitting-off in hypergraphs
• Almost-tight bounds on preserving cuts in classes of submodular hypergraphs
• Splitting-off in hypergraphs
• Online algorithms for spectral hypergraph sparsification
• Online algorithms for spectral hypergraph sparsification
• Hypergraph connectivity augmentation in strongly polynomial time
• On approximability of _2² min-sum clustering
• A theory of spectral CSP sparsification
• Near-optimal hypergraph sparsification in insertion-only and bounded-deletion streams

This page was built for publication: Spectral hypergraph sparsification via chaining

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6410246)