Search Results

Documents authored by Putterman, Aaron

Document
DOI: 10.4230/LIPIcs.CCC.2026.2
Bounded-Independence Sampling of Edges for Combinatorial Graph Properties

Authors: Aaron Putterman, Salil Vadhan, and Vadim Zaripov

Published in: LIPIcs, Volume 383, 41st Computational Complexity Conference (CCC 2026)

Abstract
Random subsampling of edges is a commonly employed technique in graph algorithms, underlying a vast array of modern algorithmic breakthroughs. Unfortunately, using this technique often leads to randomized algorithms with no clear path to derandomization because the analyses rely on a union bound over exponentially many events. In this work, we revisit this goal of derandomizing randomized sampling in graphs. We give several results related to bounded-independence edge subsampling, and in the process of doing so, generalize several of the results of Alon and Nussboim (FOCS 2008), who studied bounded-independence analogues of random graphs (which can be viewed as edge subsamples of the complete graph). Most notably, we show: 1) O(log(m))-wise independence suffices for preserving connectivity when sampling at rate 1/2 in a graph with minimum cut ≥ κ log(m) with probability 1 - 1/poly(m) (for a sufficiently large constant κ). 2) O(log(m))-wise (1/poly(m))-almost independence suffices for ensuring cycle-freeness when sampling at rate 1/2 in a graph with minimum cycle length ≥ κ log(m) with probability 1 - 1/poly(m) (for a sufficiently large constant κ). 3) If we relax to arbitrary distributions, we show there is an explicit distribution with marginals ≤ 1/2 generated using O(log(m)log log(m)) random bits such that in a graph with minimum cut ≥ κ log(m) (for a sufficiently large constant κ), a sample from the distribution has is still connected with probability 1- 1/poly(m). To demonstrate the utility of our results, we revisit the classic problem of using parallel algorithms to find graphic matroid bases, first studied in the work of Karp, Upfal, and Wigderson (FOCS 1985). In this regime, we show that the optimal algorithms of Khanna, Putterman, and Song (arxiv 2025) can be explicitly derandomized while maintaining near-optimality.
Cite as

Aaron Putterman, Salil Vadhan, and Vadim Zaripov. Bounded-Independence Sampling of Edges for Combinatorial Graph Properties. In 41st Computational Complexity Conference (CCC 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 383, pp. 2:1-2:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{putterman_et_al:LIPIcs.CCC.2026.2,
  author =	{Putterman, Aaron and Vadhan, Salil and Zaripov, Vadim},
  title =	{{Bounded-Independence Sampling of Edges for Combinatorial Graph Properties}},
  booktitle =	{41st Computational Complexity Conference (CCC 2026)},
  pages =	{2:1--2:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-437-6},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{383},
  editor =	{Moshkovitz, Dana},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2026.2},
  URN =		{urn:nbn:de:0030-drops-270444},
  doi =		{10.4230/LIPIcs.CCC.2026.2},
  annote =	{Keywords: Graphs, random sampling}
}
Document
DOI: 10.4230/LIPIcs.CP.2026.8
Classification of Non-Redundancy of Boolean Predicates of Arity 4

Authors: Joshua Brakensiek, Venkatesan Guruswami, and Aaron Putterman

Published in: LIPIcs, Volume 379, 32nd International Conference on Principles and Practice of Constraint Programming (CP 2026)

Abstract
Given a constraint satisfaction problem (CSP) predicate P ⊆ D^r, the non-redundancy (NRD) of P is the maximum-sized instance on n variables such that for every clause of the instance, there is an assignment which satisfies all clauses but that one. The study of NRD for various CSPs is an active area of research which combines ideas from extremal combinatorics, logic, lattice theory, and other techniques. Complete classifications are known in the cases r = 2 and (|D| = 2, r = 3). In this paper, we give a near-complete classification of the case (|D| = 2, r = 4). Of the 400 distinct non-trivial Boolean predicates of arity 4, we implement an algorithmic procedure which perfectly classifies 397 of them. Of the remaining three, we solve two by reducing to extremal combinatorics problems - leaving the last one as an open question. Along the way, we identify the first Boolean predicate whose non-redundancy asymptotics are non-polynomial.
Cite as

Joshua Brakensiek, Venkatesan Guruswami, and Aaron Putterman. Classification of Non-Redundancy of Boolean Predicates of Arity 4. In 32nd International Conference on Principles and Practice of Constraint Programming (CP 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 379, pp. 8:1-8:24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{brakensiek_et_al:LIPIcs.CP.2026.8,
  author =	{Brakensiek, Joshua and Guruswami, Venkatesan and Putterman, Aaron},
  title =	{{Classification of Non-Redundancy of Boolean Predicates of Arity 4}},
  booktitle =	{32nd International Conference on Principles and Practice of Constraint Programming (CP 2026)},
  pages =	{8:1--8:24},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-432-1},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{379},
  editor =	{Beldiceanu, Nicolas},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CP.2026.8},
  URN =		{urn:nbn:de:0030-drops-266412},
  doi =		{10.4230/LIPIcs.CP.2026.8},
  annote =	{Keywords: constraint satisfaction problem, redundancy}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2026.44
Multiplicative Error Set System Sparsification: A Simpler Proof via Chain Length Contraction

Authors: Joshua Brakensiek, Venkatesan Guruswami, and Aaron Putterman

Published in: LIPIcs, Volume 374, 53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026)

Abstract
The chain length of a set family 𝒮 ⊆ 2^[m] is the largest ascending sequence of sets in containment order in the union-closure of S. In this work, we provide a significantly simpler and more optimal characterization of the sparsifiability of set systems in terms of their chain length, improving on the work of Brakensiek and Guruswami [STOC 2025]. Our proof relies on a generalization of Karger’s [SODA 1993] famous contraction algorithm and its recent linear algebraic extensions [Khanna-Putterman-Sudan SODA 2024], and our resulting bounds show that, just as VC dimension characterizes the additive sparsifiability of a set system, chain length governs the multiplicative sparsifiability. As a corollary, we obtain improved bounds for weighted CSP sparsification.
Cite as

Joshua Brakensiek, Venkatesan Guruswami, and Aaron Putterman. Multiplicative Error Set System Sparsification: A Simpler Proof via Chain Length Contraction. In 53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 374, pp. 44:1-44:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{brakensiek_et_al:LIPIcs.ICALP.2026.44,
  author =	{Brakensiek, Joshua and Guruswami, Venkatesan and Putterman, Aaron},
  title =	{{Multiplicative Error Set System Sparsification: A Simpler Proof via Chain Length Contraction}},
  booktitle =	{53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026)},
  pages =	{44:1--44:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-428-4},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{374},
  editor =	{Bhattacharya, Sayan and Nanongkai, Danupon and Benedikt, Michael and Puppis, Gabriele},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2026.44},
  URN =		{urn:nbn:de:0030-drops-264331},
  doi =		{10.4230/LIPIcs.ICALP.2026.44},
  annote =	{Keywords: constraint satisfaction problem, chain length, sparsification, VC dimension}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2026.124
An Õ(n^{3/7}) Round Parallel Algorithm for Matroid Bases

Authors: Sanjeev Khanna, Aaron Putterman, and Junkai Song

Published in: LIPIcs, Volume 374, 53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026)

Abstract
We study the parallel (adaptive) complexity of the classic problem of finding a basis in an n-element matroid, given access via an independence oracle. In this model, the algorithm may submit polynomially many independence queries in each round, and the central question is: how many rounds are necessary and sufficient to find a basis? Karp, Upfal, and Wigderson (FOCS 1985, JCSS 1988; hereafter KUW) initiated this study, showing that O(√n) adaptive rounds suffice for any matroid, and that Ω̃(n^{1/3}) rounds are necessary even for partition matroids. This left a substantial gap that persisted for nearly four decades, until Khanna, Putterman, and Song (FOCS 2025; hereafter KPS) achieved Õ(n^{7/15}) rounds, the first improvement since KUW. In this work, we make another conceptual advance beyond KPS, giving a new algorithm that finds a matroid basis in Õ(n^{3/7}) rounds. We develop a structural and algorithmic framework that brings a new lens to the analysis of random circuits, moving from reasoning about individual elements to understanding how dependencies span multiple elements simultaneously. Specifically, our framework introduces three new ideas: 1) A new subset-based decomposition that provides precise guarantees on how random circuits intersect groups of elements, yet remains computable in few adaptive rounds. 2) A new method for identifying and removing redundant elements in bulk, based on short circuit witnesses that certify redundancy across large portions of the matroid. 3) An adaptive early-stopping strategy that uses the evolving structure of the matroid to decide when to contract or delete, preventing wasted rounds. Each of these contributions, in isolation, already yields meaningful improvements over the round complexity achieved in KPS; their combination enables our main result of Õ(n^{3/7}) rounds. As further consequences, incorporating our improved basis-finding algorithm into known reductions yields an Õ(n^{17/21})-round parallel algorithm for matroid intersection, as well as an Õ(n^{3/7})-round parallel algorithm for approximate monotone submodular maximization under a matroid constraint.
Cite as

Sanjeev Khanna, Aaron Putterman, and Junkai Song. An Õ(n^{3/7}) Round Parallel Algorithm for Matroid Bases. In 53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 374, pp. 124:1-124:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{khanna_et_al:LIPIcs.ICALP.2026.124,
  author =	{Khanna, Sanjeev and Putterman, Aaron and Song, Junkai},
  title =	{{An Õ(n^\{3/7\}) Round Parallel Algorithm for Matroid Bases}},
  booktitle =	{53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026)},
  pages =	{124:1--124:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-428-4},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{374},
  editor =	{Bhattacharya, Sayan and Nanongkai, Danupon and Benedikt, Michael and Puppis, Gabriele},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2026.124},
  URN =		{urn:nbn:de:0030-drops-265130},
  doi =		{10.4230/LIPIcs.ICALP.2026.124},
  annote =	{Keywords: parallel algorithms, matroids}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2026.125
Optimal Parallel Basis Finding in Graphic and Related Matroids

Authors: Sanjeev Khanna, Aaron Putterman, and Junkai Song

Published in: LIPIcs, Volume 374, 53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026)

Abstract
We study the parallel complexity of finding a basis of a graphic matroid under independence-oracle access. Karp, Upfal, and Wigderson (FOCS 1985, JCSS 1988) initiated the study of this problem and established two algorithms for finding a spanning forest: one running in O(log m) rounds with m^{Θ(log m)} queries, and another, for any d ∈ ℤ^+, running in O(m^{2/d}) rounds with Θ(m^d) queries. A key open question they posed was whether one could simultaneously achieve polylogarithmic rounds and polynomially many queries. We give a deterministic algorithm that uses O(log m) adaptive rounds and poly(m) non-adaptive queries per round to return a spanning forest on m edges, and complement this result with a matching Ω(log m) lower bound for any (even randomized) algorithm with poly(m) queries per round. Thus, the adaptive round complexity for graphic matroids is characterized exactly, settling this long-standing problem. Beyond graphs, we show that our framework also yields an O(log m)-round, poly(m)-query algorithm for any binary matroid satisfying a smooth circuit counting property, implying, among others, an optimal O(log m)-round parallel algorithms for finding bases of cographic matroids. Finally, we conjecture a natural strengthening of known circuit-counting bounds for the much broader class of regular matroids and even an extension to so-called max-flow min-cut matroids; assuming it, our algorithm achieves the same O(log m) rounds and poly(m) queries for all such matroids - which includes graphic and cographic matroids as special cases.
Cite as

Sanjeev Khanna, Aaron Putterman, and Junkai Song. Optimal Parallel Basis Finding in Graphic and Related Matroids. In 53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 374, pp. 125:1-125:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{khanna_et_al:LIPIcs.ICALP.2026.125,
  author =	{Khanna, Sanjeev and Putterman, Aaron and Song, Junkai},
  title =	{{Optimal Parallel Basis Finding in Graphic and Related Matroids}},
  booktitle =	{53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026)},
  pages =	{125:1--125:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-428-4},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{374},
  editor =	{Bhattacharya, Sayan and Nanongkai, Danupon and Benedikt, Michael and Puppis, Gabriele},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2026.125},
  URN =		{urn:nbn:de:0030-drops-265143},
  doi =		{10.4230/LIPIcs.ICALP.2026.125},
  annote =	{Keywords: parallel algorithms, matroids}
}
Document
DOI: 10.4230/LIPIcs.CCC.2025.19
Characterizing the Distinguishability of Product Distributions Through Multicalibration

Authors: Cassandra Marcussen, Aaron Putterman, and Salil Vadhan

Published in: LIPIcs, Volume 339, 40th Computational Complexity Conference (CCC 2025)

Abstract
Given a sequence of samples x_1, … , x_k promised to be drawn from one of two distributions X₀, X₁, a well-studied problem in statistics is to decide which distribution the samples are from. Information theoretically, the maximum advantage in distinguishing the two distributions given k samples is captured by the total variation distance between X₀^{⊗k} and X₁^{⊗k}. However, when we restrict our attention to efficient distinguishers (i.e., small circuits) of these two distributions, exactly characterizing the ability to distinguish X₀^{⊗k} and X₁^{⊗k} is more involved and less understood. In this work, we give a general way to reduce bounds on the computational indistinguishability of X₀ and X₁ to bounds on the information-theoretic indistinguishability of some specific, related variables X̃₀ and X̃₁. As a consequence, we prove a new, tight characterization of the number of samples k needed to efficiently distinguish X₀^{⊗k} and X₁^{⊗k} with constant advantage as k = Θ(d_H^{-2}(X̃₀, X̃₁)), which is the inverse of the squared Hellinger distance d_H between two distributions X̃₀ and X̃₁ that are computationally indistinguishable from X₀ and X₁. Likewise, our framework can be used to re-derive a result of Halevi and Rabin (TCC 2008) and Geier (TCC 2022), proving nearly-tight bounds on how computational indistinguishability scales with the number of samples for arbitrary product distributions. At the heart of our work is the use of the Multicalibration Theorem (Hébert-Johnson, Kim, Reingold, Rothblum 2018) in a way inspired by recent work of Casacuberta, Dwork, and Vadhan (STOC 2024). Multicalibration allows us to relate the computational indistinguishability of X₀, X₁ to the statistical indistinguishability of X̃₀, X̃₁ (for lower bounds on k) and construct explicit circuits to distinguish between X̃₀, X̃₁ and consequently X₀, X₁ (for upper bounds on k).
Cite as

Cassandra Marcussen, Aaron Putterman, and Salil Vadhan. Characterizing the Distinguishability of Product Distributions Through Multicalibration. In 40th Computational Complexity Conference (CCC 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 339, pp. 19:1-19:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{marcussen_et_al:LIPIcs.CCC.2025.19,
  author =	{Marcussen, Cassandra and Putterman, Aaron and Vadhan, Salil},
  title =	{{Characterizing the Distinguishability of Product Distributions Through Multicalibration}},
  booktitle =	{40th Computational Complexity Conference (CCC 2025)},
  pages =	{19:1--19:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-379-9},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{339},
  editor =	{Srinivasan, Srikanth},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2025.19},
  URN =		{urn:nbn:de:0030-drops-237130},
  doi =		{10.4230/LIPIcs.CCC.2025.19},
  annote =	{Keywords: Multicalibration, computational distinguishability}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2025.107
A Theory of Spectral CSP Sparsification

Authors: Sanjeev Khanna, Aaron Putterman, and Madhu Sudan

Published in: LIPIcs, Volume 334, 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025)

Abstract
We initiate the study of spectral sparsification for instances of Constraint Satisfaction Problems (CSPs). In particular, we introduce a notion of the spectral energy of a fractional assignment for a Boolean CSP instance, and define a spectral sparsifier as a weighted subset of constraints that approximately preserves this energy for all fractional assignments. Our definition not only strengthens the combinatorial notion of a CSP sparsifier but also extends well-studied concepts such as spectral sparsifiers for graphs and hypergraphs. Recent work by Khanna, Putterman, and Sudan [SODA 2024] demonstrated near-linear sized combinatorial sparsifiers for a broad class of CSPs, which they term field-affine CSPs. Our main result is a polynomial-time algorithm that constructs a spectral CSP sparsifier of near-quadratic size for all field-affine CSPs. This class of CSPs includes graph (and hypergraph) cuts, XORs, and more generally, any predicate which can be written as P(x₁, … x_r) = 𝟏[∑ a_i x_i ≠ b mod p]. Based on our notion of the spectral energy of a fractional assignment, we also define an analog of the second eigenvalue of a CSP instance. We then show an extension of Cheeger’s inequality for all even-arity XOR CSPs, showing that this second eigenvalue loosely captures the "expansion" of the underlying CSP. This extension specializes to the case of Cheeger’s inequality when all constraints are even XORs and thus gives a new generalization of this powerful inequality which converts the combinatorial notion of expansion to an analytic property. Perhaps the most important effect of spectral sparsification is that it has led to certifiable sparsifiers for graphs and hypergraphs. This aspect remains open in our case even for XOR CSPs since the eigenvalues we describe in our Cheeger inequality are not known to be efficiently computable. Computing this efficiently, and/or finding other ways to certifiably sparsify CSPs are open questions emerging from our work. Another important open question is determining which classes of CSPs have near-linear size spectral sparsifiers.
Cite as

Sanjeev Khanna, Aaron Putterman, and Madhu Sudan. A Theory of Spectral CSP Sparsification. In 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 334, pp. 107:1-107:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{khanna_et_al:LIPIcs.ICALP.2025.107,
  author =	{Khanna, Sanjeev and Putterman, Aaron and Sudan, Madhu},
  title =	{{A Theory of Spectral CSP Sparsification}},
  booktitle =	{52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025)},
  pages =	{107:1--107:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-372-0},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{334},
  editor =	{Censor-Hillel, Keren and Grandoni, Fabrizio and Ouaknine, Jo\"{e}l and Puppis, Gabriele},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2025.107},
  URN =		{urn:nbn:de:0030-drops-234840},
  doi =		{10.4230/LIPIcs.ICALP.2025.107},
  annote =	{Keywords: Sparsification, sketching, hypergraphs}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2025.108
Near-Optimal Hypergraph Sparsification in Insertion-Only and Bounded-Deletion Streams

Authors: Sanjeev Khanna, Aaron Putterman, and Madhu Sudan

Published in: LIPIcs, Volume 334, 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025)

Abstract
We study the problem of constructing hypergraph cut sparsifiers in the streaming model where a hypergraph on n vertices is revealed either via an arbitrary sequence of hyperedge insertions alone (insertion-only streaming model) or via an arbitrary sequence of hyperedge insertions and deletions (dynamic streaming model). For any ε ∈ (0,1), a (1 ± ε) hypergraph cut-sparsifier of a hypergraph H is a reweighted subgraph H' whose cut values approximate those of H to within a (1 ± ε) factor. Prior work shows that in the static setting, one can construct a (1 ± ε) hypergraph cut-sparsifier using Õ(nr/ε²) bits of space [Chen-Khanna-Nagda FOCS 2020], and in the setting of dynamic streams using Õ(nrlog m/ε²) bits of space [Khanna-Putterman-Sudan FOCS 2024]; here the Õ notation hides terms that are polylogarithmic in n, and we use m to denote the total number of hyperedges in the hypergraph. Up until now, the best known space complexity for insertion-only streams has been the same as that for the dynamic streams. This naturally poses the question of understanding the complexity of hypergraph sparsification in insertion-only streams. Perhaps surprisingly, in this work we show that in insertion-only streams, a (1 ± ε) cut-sparsifier can be computed in Õ(nr/ε²) bits of space, matching the complexity of the static setting. As a consequence, this also establishes an Ω(log m) factor separation between the space complexity of hypergraph cut sparsification in insertion-only streams and dynamic streams, as the latter is provably known to require Ω(nr log m) bits of space. To better explain this gap, we then show a more general result: namely, if the stream has at most k hyperedge deletions then Õ(n r log k/ε²) bits of space suffice for hypergraph cut sparsification. Thus the space complexity smoothly interpolates between the insertion-only regime (k = 0) and the fully dynamic regime (k = m). Our algorithmic results are driven by a key technical insight: once sufficiently many hyperedges have been inserted into the stream (relative to the number of allowed deletions), we can significantly reduce the underlying hypergraph by size by irrevocably contracting large subsets of vertices. Finally, we complement this result with an essentially matching lower bound of Ω(n r log(k/n)) bits, thus providing essentially a tight characterization of the space complexity for hypergraph cut-sparsification across a spectrum of streaming models.
Cite as

Sanjeev Khanna, Aaron Putterman, and Madhu Sudan. Near-Optimal Hypergraph Sparsification in Insertion-Only and Bounded-Deletion Streams. In 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 334, pp. 108:1-108:11, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{khanna_et_al:LIPIcs.ICALP.2025.108,
  author =	{Khanna, Sanjeev and Putterman, Aaron and Sudan, Madhu},
  title =	{{Near-Optimal Hypergraph Sparsification in Insertion-Only and Bounded-Deletion Streams}},
  booktitle =	{52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025)},
  pages =	{108:1--108:11},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-372-0},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{334},
  editor =	{Censor-Hillel, Keren and Grandoni, Fabrizio and Ouaknine, Jo\"{e}l and Puppis, Gabriele},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2025.108},
  URN =		{urn:nbn:de:0030-drops-234851},
  doi =		{10.4230/LIPIcs.ICALP.2025.108},
  annote =	{Keywords: Sparsification, sketching, hypergraphs}
}
Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

Please try again later or send an E-mail
© 2023-2026 Schloss Dagstuhl – LZI GmbH Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact