DROPS

Document

DOI: 10.4230/LIPIcs.ESA.2026.70

Streaming with Catalytic Memory

Authors: Tamara Kaplan, Nimrod Kaplan, and Haim Kaplan

Published in: LIPIcs, Volume 388, 34th Annual European Symposium on Algorithms (ESA 2026)

Abstract

We introduce a streaming model that uses both catalytic and regular memory. In this model, we show how to exactly compute the frequency moments using a logarithmic number of bits of regular memory and a polynomial number of bits of catalytic memory. More generally, we show how to compute arbitrary polynomials of the item frequencies exactly within the same space bounds. As an application, we obtain catalytic streaming algorithms that exactly compute the number of distinct elements in a stream, count the number of triangles (or any other small subgraph) in a graph whose edges arrive in a stream, and identify heavy hitters. Our algorithms for frequency moments perform a constant number of passes over the stream, and for polynomial evaluation, we require one more pass than the degree of the polynomial. In particular, for the second moment, we perform three passes over the stream. By relating our catalytic streaming model to the catalytic communication model introduced in [Pyne et al., 2025], we show that catalytic memory is not useful for any one pass streaming algorithms. For lower bounds on multi pass streaming algorithms, the impossibility results of [Pyne et al., 2025] are not strong enough. However, using a different technique, we show that computing the second frequency moment cannot be achieved by a two pass catalytic streaming algorithm that satisfies certain natural assumptions.

Cite as

Tamara Kaplan, Nimrod Kaplan, and Haim Kaplan. Streaming with Catalytic Memory. In 34th Annual European Symposium on Algorithms (ESA 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 388, pp. 70:1-70:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{kaplan_et_al:LIPIcs.ESA.2026.70,
  author =	{Kaplan, Tamara and Kaplan, Nimrod and Kaplan, Haim},
  title =	{{Streaming with Catalytic Memory}},
  booktitle =	{34th Annual European Symposium on Algorithms (ESA 2026)},
  pages =	{70:1--70:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-445-1},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{388},
  editor =	{Bille, Philip and Pettie, Seth and Storandt, Sabine},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2026.70},
  URN =		{urn:nbn:de:0030-drops-272060},
  doi =		{10.4230/LIPIcs.ESA.2026.70},
  annote =	{Keywords: Catalytic memory, streaming algorithms, frequency moments, space complexity, polynomial evaluation}
}

Document

DOI: 10.4230/LIPIcs.CCC.2026.25

Polynomial Identity Testing for Read-4 Arithmetic Formulas

Authors: Nimrod Kaplan and Amir Shpilka

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

Abstract

We present the first algorithms for polynomial identity testing (PIT) of read-4 arithmetic formulas in the non-multilinear setting. Specifically, we give a polynomial-time PIT algorithm in the whitebox model and a quasi-polynomial-time algorithm in the blackbox model. Since our techniques are based on proving hardness of representation results, we extend our algorithms to orbits of read-4 formulas under the action of the affine linear group. Prior to our work, no subexponential white- or blackbox algorithms were known for this class of formulas. All our results hold over any field 𝔽 with char(𝔽) = 0 or char(𝔽) ≥ 5. Prior work addressed only restricted cases. Anderson, van Melkebeek, and Volkovich (Computational Complexity, 2015) studied multilinear read-k formulas, giving a polynomial-time whitebox PIT algorithm and a quasi-polynomial-time blackbox algorithm. Without the multilinearity restriction, Mahajan, Rao, and Sreenivasaiah (TCS, 2014) gave polynomial-time whitebox algorithms for read-2 and read-3 formulas, Prakriya (Doctoral Thesis, 2019) obtained quasi-polynomial-time blackbox PIT algorithm for both read-2 and read-3 formulas. Independently, Shamir (Master’s Thesis, 2022) obtained a quasi-polynomial-time blackbox PIT algorithm for read-2 formulas. For bounded-depth read-k formulas, Agrawal, Saha, Saptharishi, and Saxena (SICOMP, 2016) obtained a polynomial-time blackbox algorithm in the non-multilinear case. The running time of their algorithm is n^{k^{2^Δ}} for read-k, depth-Δ formulas, and hence it is applicable only to constant depth. Partial derivatives are a central tool in the study of deterministic PIT for bounded-read formulas. However, for non-multilinear RkF, differentiation may increase the number of reads. To address this, we develop new structural results that ensure "nice behavior" of derivatives. Specifically, we introduce a new Fragmentation Lemma that reduces the PIT problem for general RkFs to simpler models via differentiation. In addition, we define the notion of dominating degree patterns and show that, in certain cases, taking partial derivatives with respect to these patterns preserves the read count.

Cite as

Nimrod Kaplan and Amir Shpilka. Polynomial Identity Testing for Read-4 Arithmetic Formulas. In 41st Computational Complexity Conference (CCC 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 383, pp. 25:1-25:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{kaplan_et_al:LIPIcs.CCC.2026.25,
  author =	{Kaplan, Nimrod and Shpilka, Amir},
  title =	{{Polynomial Identity Testing for Read-4 Arithmetic Formulas}},
  booktitle =	{41st Computational Complexity Conference (CCC 2026)},
  pages =	{25:1--25:18},
  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.25},
  URN =		{urn:nbn:de:0030-drops-270678},
  doi =		{10.4230/LIPIcs.CCC.2026.25},
  annote =	{Keywords: algebraic complexity theory, polynomial identity testing, PIT, bounded read formulas}
}

Search Results

Documents authored by Kaplan, Nimrod

Streaming with Catalytic Memory

Abstract

Cite as

Polynomial Identity Testing for Read-4 Arithmetic Formulas

Abstract

Cite as

Thanks for your feedback!

Could not send message