Linear Sketching Hypergraph 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 \emph{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 $\widetilde{O}(n r \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$. We then complement this with a nearly-matching lower bound of $\Omega(nr \log(m/n) / \log(n))$ bits for any $\epsilon \in (0,1)$.
This immediately gives a dynamic streaming algorithm for hypergraph cut sparsification with an identical space complexity, improving on the previous best known bound of $\widetilde{O}(n r^2 \log^4(m) / \epsilon^2)$ bits of space. Our constructions rely on several new techniques, including an improved analysis of the error accumulation when iteratively constructing sparsifiers, a pre-processing linear sketch which limits the sizes of hypergraphs which arise in our reconstruction process, and a method we call random fingerprinting, which is used to break correlations between hyperedges in order to limit the redundancy of our linear sketch.