Near-Optimal Size Linear Sketches for Hypergraph Cut Sparsifiers

A$(1\pm\epsilon)$-sparsifier of a hypergraph$G(V, E)$is a (weighted) subgraph that preserves the value of every cut to within a$(1\pm\epsilon)$-factor. It is known that every hypergraph with$n$vertices admits a$(1 \pm \epsilon)$-sparsifier with$\tilde{O}(n/{\epsilon}^{2})$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$\tilde{O}(nr\log(m)/\epsilon^{2})$bits which with high probability contains sufficient information to recover a$(1\pm\epsilon)$cut-sparsifier with$\tilde{O}(n/\epsilon^{2})$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$\tilde{O}(nr^{2}\log^{4}({m})/\epsilon^{2})$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$\epsilon\in(0,1)$, one needs$\Omega(nr\log(m/n)/\log(n))$bits to construct a$(1\pm\epsilon)$-sparsifier via linear sketching, thus showing that our linear sketch achieves an optimal dependence on both$r$and$\log(m)$. The starting point for our improved algorithm is importance sampling of hyperedges based on the new notion of$k$-cut strength introduced in the recent work of Quanrud (SODA 2024). The natural algorithm based on this concept leads to$\log m$levels of sampling where errors can potentially accumulate, and this accounts for the polylog$(m)$losses in the sketch size of the natural algorithm. We develop a more intricate analysis of the accumulation in error to show most levels do not contribute to the error and actual loss is only polylog$(n)$. Combining with careful preprocessing (and analysis) this enables us to get rid of all extraneous$\log m$factors in the sketch size, but the quadratic dependence on$r$remains. This dependence originates from use of correlated$\ell_{0}$-samplers to recover a large number of low-strength edges in a hypergraph simultaneously by looking at neighborhoods of individual vertices. In graphs, this leads to discovery of$\Omega(n)$edges in a single shot, whereas in hypergraphs, this may potentially only reveal$O$($n$/$r$) new edges, thus requiring$\Omega(r)$rounds of recovery. To remedy this we introduce a new technique of random fingerprinting of hyperedges which effectively eliminates the correlations created by large arity hyperedges, and leads to a scheme for recovering hyperedges of low strength with an optimal dependence on$r$. Putting all these ingredients together yields our linear sketching algorithm. Our lower bound is established by a reduction from the universal relation problem in the one-way communication setting.