{"ID":2851969,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2510.18180","arxiv_id":"2510.18180","title":"Nearly Space-Optimal Graph and Hypergraph Sparsification in Insertion-Only Data Streams","abstract":"We study the problem of graph and hypergraph sparsification in insertion-only data streams. The input is a hypergraph $H=(V, E, w)$ with $n$ nodes, $m$ hyperedges, and rank $r$, and the goal is to compute a hypergraph $\\widehat{H}$ that preserves the energy of each vector $x \\in \\mathbb{R}^n$ in $H$, up to a small multiplicative error. In this paper, we give a streaming algorithm that achieves a $(1+\\varepsilon)$-approximation, using $\\frac{rn}{\\varepsilon^2} \\log^2 n \\log r \\cdot\\text{poly}(\\log \\log m)$ bits of space, matching the sample complexity of the best known offline algorithm up to $\\text{poly}(\\log \\log m)$ factors. Our approach also provides a streaming algorithm for graph sparsification that achieves a $(1+\\varepsilon)$-approximation, using $\\frac{n}{\\varepsilon^2} \\log n \\cdot\\text{poly}(\\log\\log n)$ bits of space, improving the current bound by $\\log n$ factors. Furthermore, we give a space-efficient streaming algorithm for min-cut approximation. Along the way, we present an online algorithm for $(1+\\varepsilon)$-hypergraph sparsification, which is optimal up to poly-logarithmic factors. As a result, we achieve $(1+\\varepsilon)$-hypergraph sparsification in the sliding window model, with space optimal up to poly-logarithmic factors. Lastly, we give an adversarially robust algorithm for hypergraph sparsification using $\\frac{n}{\\varepsilon^2} \\cdot\\text{poly}(r, \\log n, \\log r, \\log \\log m)$ bits of space.","short_abstract":"We study the problem of graph and hypergraph sparsification in insertion-only data streams. The input is a hypergraph $H=(V, E, w)$ with $n$ nodes, $m$ hyperedges, and rank $r$, and the goal is to compute a hypergraph $\\widehat{H}$ that preserves the energy of each vector $x \\in \\mathbb{R}^n$ in $H$, up to a small mult...","url_abs":"https://arxiv.org/abs/2510.18180","url_pdf":"https://arxiv.org/pdf/2510.18180v1","authors":"[\"Vincent Cohen-Addad\",\"David P. Woodruff\",\"Shenghao Xie\",\"Samson Zhou\"]","published":"2025-10-21T00:10:05Z","proceeding":"cs.DS","tasks":"[\"cs.DS\"]","methods":"[]","has_code":false}