Answers are grounded in this paper and cite their sources.
A (1 ± ε)-sparsifier of a hypergraph $G(V,E)$ is a (weighted) subgraph that preserves the value of every cut to within a (1 ± ε)-factor. It is known that every hypergraph with n vertices admits a (1 ± ε)-sparsifier with Õ(n/ε²) hyperedges. In this work, we explore the task of building such a sparsifier by using only linear measurements (a linear sketch) over the hyperedges of G, and provide nearly-matching upper and lower bounds for this task. Specifically, we show that there is a randomized linear sketch of size O(n r log(m) / ε²) bits which with high probability contains sufficient information to recover a (1 ± ε) cut-sparsifier with Õ(n/ε²) hyperedges for any hypergraph with at most m edges each of which has arity bounded by r. This immediately gives a dynamic streaming algorithm for hypergraph cut sparsification with an identical space complexity, improving on the previous best known bound of O(n r² log⁴(m) / ε²) bits of space (Guha, McGregor, and Tench, PODS 2015). We complement our algorithmic result above with a nearly-matching lower bound. We show that for every ε ∈ (0,1), one needs Ω(nr log(m/n) / log(n)) bits to construct a (1 ± ε)-sparsifier via linear sketching, thus showing that our linear sketch achieves an optimal dependence on both r and log(m).
No takes yet. Share an insight, caveat, or question.
Khanna et al. (2024) studied this question.
Synapse has enriched 8 closely related papers on similar clinical questions. Consider them for comparative context: