Pith. sign in

REVIEW 3 major objections 4 minor 1 cited by

Catalytic Computing and Register Programs Beyond Log-Depth

T0 review · 3 major / 4 minor · reviewed 2026-08-16 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read Catalytic memory with near-polynomial clean tape evaluates every SAC^2 circuit in O(log^2 n / log log n) work space.

desk verdict New catalytic-space upper bounds that would be important if the proof closed, but there is a genuine gap in Lemma 3.7 that leaves Theorem 1.1 unproven as written. read the letter →

arxiv 2504.17412 v1 pith:RMCXDX26 submitted 2025-04-24 cs.CC

Yaroslav Alekseev , Yuval Filmus , Ian Mertz , Alexander Smal , Antoine Vinciguerra This is my paper · ORCID
classification cs.CC MSC 68Q1568Q17
keywords catalyticspaceregisterprogramsSAC^2circuitcomplexityNChierarchymatrixpoweringpolynomialrepresentationspace-boundedcomputation
topics P versus NP
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

This paper tries to show that catalytic memory—a scratch tape that must be returned to its original contents—can evaluate circuits of depth O($log^{2}$ n) using less free work space than previous methods. Concretely, it claims that for every epsilon > 0, the class $SAC^{2}$ of polynomial-size, depth-O($log^{2}$ n) circuits with bounded fan-in AND and unbounded fan-in OR gates lies in CSPACE(O($log^{2}$ n / log log n), $2^{{O(log^{1+epsilon}}$ n)}). That is an O(log log n) improvement in the work tape over the prior best, at the price of a catalytic tape of near-polynomial size. The argument runs through register programs: sequences of register updates and input accesses that are clean (restorable) and composable, and that can be simulated on a catalytic machine. The paper also builds register programs for matrix powering with sublinear recursive access to the matrix, a step toward showing $NC^{2}$ subseteq CL.

What carries the argument

The machinery that carries the argument is the clean register program together with its composition rule. A clean program updates some registers by adding a polynomial in the others and leaves all remaining registers untouched; the composition lemma (Lemma 2.1) plugs one clean program's output into another's input, multiplying the recursive-call counts and adding the inner program's cost to each outer call. This lets the paper build layered circuits out of gate programs. The other key ingredient is polynomial representation: Theorem 3.3 rewrites any degree-d homogeneous polynomial as sum_i alpha_i (sum_j beta_{i,j} x_j)^d, so evaluating a circuit reduces to summing powers of linear forms, which the built-in powering program handles with four recursive calls. Lemma 3.9 carries this to circuits by bounding the degree and term count of a depth-d circuit's representing polynomial. These pieces combine in Lemma 3.8, which merges circuit layers, and in Lemma 2.2, which converts the final register program into a catalytic Turing machine.

What would settle it

Apply the proof of Lemma 3.7 to a polynomial whose monomials all contain a common variable, such as the expanded form of (x_1 + x_2 + ... + x_m)^d; the lemma's per-monomial programs each read that variable, and Lemma 2.1 multiplies reads when programs are composed. Counting the total reads of x_1 in the constructed program will show whether it stays at 64 or grows with the number of monomials, which decides whether the main proof's key step is sound.

Watch

Extended reading notes

Core claim

The central discovery is a way to evaluate circuits that are too deep for catalytic logspace by compressing many circuit layers into one polynomial and then computing that polynomial with a register program that makes only a constant number of reads of each input. Lemma 3.9 shows that a depth-d circuit with fan-in-2 AND gates and fan-in ell OR gates can be represented by a degree-2^d polynomial with at most $ell^{{2^d}}$ terms over Z. Lemma 3.7 turns such a representation into a clean register program using 64 recursive calls per input, O(t $p^{2}$ log p) basic instructions, and O(tp) registers over Z_p, where t is the number of terms and p > d,t is prime. Combining these via the composition lemma and choosing d = epsilon log log n gives Corollary 3.9.1, and applying the layer-merging lemma to the remaining $log^{2}$ n / d layers yields Theorem 1.1. For matrix powering, the paper decomposes M^d into a product of powers ($M^{{delta^i}}$)^{alpha_i}, connecting sublinear recursive-call programs for repeated powers to give Theorem 1.2.

Load-bearing premise

The proof's load-bearing premise is that one value of an input can be reused for free when many monomials need it; the paper's own rules for combining subroutines say that reuse should cost extra reads, so this premise is the point that must hold for the main theorem's proof to go through.

Editorial extensions

If this is right

  • Every SAC^2 circuit can be evaluated by a catalytic Turing machine with O(log^2 n / log log n) work-tape bits and 2^{O(log^{1+epsilon} n)} catalytic-tape bits, for any fixed epsilon > 0.
  • The same layered construction applies to #SAC^2, the arithmetic analogue, so counting the satisfying assignments of such circuits also fits in the same catalytic resource bounds.
  • Any problem in NC^2 inherits the SAC^2 bound, and the matrix-powering register programs show that matrix exponentiation over F_p can be done with O_epsilon(d^epsilon log d) recursive accesses to the matrix and O_epsilon(n^{exp(1/epsilon)}) registers.
  • The O(log log n) shaving is the first improvement in the free space needed for depth-log^2 n circuits in the catalytic model, suggesting that catalytic memory is a genuine resource for trading work space against cleanable auxiliary space.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • The same layer-merging scheme would, if its constant-call step can be made rigorous, generalize to SAC^k for every fixed k, replacing log^2 n by log^k n in the work-space bound; the paper only carries out the case k=2.
  • A register program that computes M^d with O(1) recursive calls to M and polynomially many registers—the natural next step after Theorem 1.2—would combine with Lemma 2.1 to put NC^2 inside CL, answering the paper's motivating question.
  • The near-polynomial catalytic tape is an artifact of choosing the prime p = 2^{O(log^{1+epsilon} n)}; a term-count bound closer to 2^{O(d)} instead of ell^{2^d} would bring Theorem 1.1 down to polynomial catalytic tape, strengthening the case for CL containing NC^2.
Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

3 major / 4 minor

Summary. The paper studies catalytic Turing machines and register programs. Its main theorem (Theorem 1.1) claims that for every ε>0, SAC^2 is contained in CSPACE(O(log^2 n / log log n), 2^{O(log^{1+ε} n)}): polynomial-size, depth-O(log^2 n) circuits with fan-in-2 AND and unbounded fan-in OR gates can be evaluated in catalytic space with near-polynomial catalytic tape. The proof decomposes an SAC^2 circuit into depth-d blocks, represents each block as a low-degree polynomial with few terms (Lemma 3.9), evaluates these polynomials by clean register programs with a constant number of recursive calls per variable (Lemma 3.7), composes the block programs (Lemma 3.8), and simulates the final program on a catalytic machine (Lemma 2.2). The paper also gives register programs for matrix powering (Theorem 1.2) as a step toward NC^2 ⊆ CL. The central technical step is a claimed O(1)-recursive-call evaluation of every (Z,d,t)-represented Boolean function with O(tp) registers.

Significance. If the proof were correct, Theorem 1.1 would be a substantial advance: it would place SAC^2, which contains TC^1, in catalytic space with o(log^2 n) work space and near-polynomial catalytic tape, improving on the previous TC^1 ⊆ CL framework and making progress on the program proposed in [Mer23]. The matrix-powering theorem is also a useful step toward NC^2 ⊆ CL. The paper is clearly structured and the clean-composition framework is a useful tool. However, the main result currently rests on an incorrect proof of Lemma 3.7, so the significance is conditional on a repair.

major comments (3)
  1. [Section 3.3, Lemma 3.7] The proof claims that every monomial u_k = x_{i_1}...x_{i_d} is symmetric and hence computable by the symmetric-function program of Lemma 3.6. This is false for monomials on a proper subset of the variables: over n=3, the monomial x_1x_2 evaluates to 1 on (1,1,0) and to 0 on (1,0,1), so it is not a function of x_1+x_2+x_3. Lemma 3.6 only computes functions of the full sum, so it cannot compute an arbitrary monomial. Moreover, even if each monomial were evaluated by a separate program on its own support, composing the t programs with the outer summation through Lemma 2.1 would multiply recursive calls by the number of monomials containing each variable, giving up to O(t) recursive calls per variable rather than the claimed 64. Since Corollary 3.9.1 and Theorem 1.1 rely on the 64-calls-per-variable bound, the main containment is not established as written.
  2. [Section 3.3, Lemma 3.7] The lemma assumes that p > max{d,t} suffices for evaluating an integer polynomial modulo p without changing the represented Boolean function. This is false for general (Z,d,t)-representations: the coefficients may be much larger than p, and reducing them modulo a small prime can create spurious zeros. For example, P(x)=5x_1+x_2 with p=5 represents the OR function over Z, but modulo 5 it sends (1,0) to 0. The polynomials produced by Lemma 3.9 do satisfy |P(x)| ≤ t on Boolean inputs, so the issue is repairable by adding an explicit value bound to the lemma, but the lemma as stated is incorrect.
  3. [Section 3.4, Theorem 1.1 proof] The proof of Theorem 1.1 chooses d ≤ ε log log n and composes h = O(log^2 n / d) layers. If the per-block program had O(t) recursive calls per variable instead of 64, the total number of recursive calls would be (O(t))^h = 2^{Ω(log^{3+ε} n)} for t = ℓ^{2^d} = 2^{O(log^{1+ε} n)}, which would destroy the claimed work-space bound. A possible repair is to evaluate the degree-2^d block polynomial directly with Corollary 3.4.1, which also gives O(1) recursive calls per variable and 2^{O(2^d log n)} registers, but this has to be worked out carefully together with the p > |P(x)| condition; the current text does not supply such a proof.
minor comments (4)
  1. [Title] The title on page 1 reads "Beyond Log-Dept h" and should be corrected to "Beyond Log-Depth".
  2. [Lemma 3.9 and Corollary 3.9.1] The exponents in "ℓ2d" and "s2d" are ambiguous in the typeset version; they should be written as ℓ^{2^d} and s^{2^d} to match the proof by induction.
  3. [Theorem 1.2 proof] The symbol ε is reused for the theorem's parameter and for the replacement 3/log δ; the authors should use a different variable in the final asymptotic rewrite to avoid confusion.
  4. [Lemma 3.4 and Lemma 3.7] The phrase "compute all these programs in parallel" is informal in a sequential instruction model; the proof should specify how input reads are shared when multiple subprograms access the same variable, or state explicitly how the recursive-call count is amortized.

Circularity Check

0 steps flagged · score 0.0 of 10

No circular derivation: Theorem 1.1 follows from prior circuit-representation and register-program lemmas, not from its own conclusion.

full rationale

The paper's derivation chain is non-circular. Theorem 1.1 is obtained by (i) representing depth-d Boolean circuits by low-degree polynomials (Lemma 3.9, proved inductively), (ii) compiling polynomial representations to clean register programs (Lemma 3.7, using the symmetric-function program of Lemma 3.6 and the Composition Lemma 2.1), (iii) compressing an SAC^2 circuit into a circuit of larger gates and applying the layer-by-layer composition Lemma 3.8, and (iv) invoking the prior simulation lemma of Buhrman et al. (Lemma 2.2) to translate register programs into catalytic machines. No parameter is fitted to data and no claimed prediction is an input by construction. The cited results [BCK+14, CM23, Sch02, BBS08] are used as lemmas with stated assumptions or reproduced arguments, not as the source of the target containment. Self-citations to [Mer20] and [Mer23] appear only as motivation for the register-program approach and are not load-bearing. There is, however, a genuine correctness gap in Lemma 3.7: its proof asserts that each monomial u_k is symmetric and hence computable by Lemma 3.6, but a monomial such as x1 x2 is not symmetric over all n variables; this affects the recursive-call bound and is a math-error concern, not a circularity. Because circularity scoring is about reduction to inputs by construction, and this gap does not make the target equivalent to an input, the circularity score is 0.

Assumptions & free parameters 2 free parameters · 4 assumptions · 0 invented entities

No new particles, forces, or objects are postulated; the ledger records only construction parameters and the model axioms the proof relies on.

free parameters (2)
  • block depth d (Theorem 1.1 construction) = d = epsilon log log n
    Chosen by the authors so that 2^d = (log n)^epsilon, balancing the recursive-call exponent against the catalytic-tape size; not an empirical fit.
  • base delta (Lemma 3.12/Theorem 1.2) = delta = 2^{3/epsilon}
    Introduced to control the exponent in the power-decomposition; the final bound is stated for all epsilon, so this is a hand-chosen construction parameter.
assumptions (4)
  • standard math Theorem 3.3 (Schinzel; Bialynicki-Birula and Schinzel): a homogeneous degree-d polynomial over F_p is a sum of at most C(n+d-1,d-1) powers of linear forms.
    Invoked in Lemma 3.4 to represent multivariate polynomials without multiplications.
  • domain assumption Lemma 2.2 (Buhrman et al. [BCK+14]): a clean register program of time t, space s over a finite ring is simulated by a catalytic machine with work space O(log t + log n + log|R|) and catalytic space O(s log|R|).
    This is the bridge from register programs to CSPACE; the paper imports it from prior work.
  • domain assumption The basic instruction in Definition 2.4 may update a register by an arbitrary polynomial over the other registers at unit cost.
    If taken literally, this makes instruction-count bounds very weak and is inconsistent with the detailed instruction counts in Figure 1; the intended cost model is not stated.
  • ad hoc to paper Each monomial u_k in a (Z,d,t)-representation is symmetric and can be computed in parallel with O(1) recursive calls per input variable.
    Asserted in Lemma 3.7 without a supporting construction; a monomial is symmetric only as a function of its own variables, and the composition rule gives no constant-read amortization.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Catalytic Computing and Register Programs Beyond Log-Depth." pith.science (2026). https://pith.science/paper/RMCXDX26

@misc{pith2026250417412,
  author       = {Pith},
  title        = {Pith review of: Catalytic Computing and Register Programs Beyond Log-Depth},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/RMCXDX26}},
  note         = {Machine review of arXiv:2504.17412}
}
abstract

In a seminal work, Buhrman et al. (STOC 2014) defined the class $CSPACE(s,c)$ of problems solvable in space $s$ with an additional catalytic tape of size $c$, which is a tape whose initial content must be restored at the end of the computation. They showed that uniform $TC^1$ circuits are computable in catalytic logspace, i.e., $CL=CSPACE(O(\log{n}), 2^{O(\log{n})})$, thus giving strong evidence that catalytic space gives $L$ strict additional power. Their study focuses on an arithmetic model called register programs, which has been a focal point in development since then. Understanding $CL$ remains a major open problem, as $TC^1$ remains the most powerful containment to date. In this work, we study the power of catalytic space and register programs to compute circuits of larger depth. Using register programs, we show that for every $\epsilon > 0$, $SAC^2 \subseteq CSPACE\left(O\left(\frac{\log^2{n}}{\log\log{n}}\right), 2^{O(\log^{1+\epsilon} n)}\right)$ This is an $O(\log \log n)$ factor improvement on the free space needed to compute $SAC^2$, which can be accomplished with near-polynomial catalytic space. We also exhibit non-trivial register programs for matrix powering, which is a further step towards showing $NC^2 \subseteq CL$.

Figures

Figures reproduced from arXiv: 2504.17412 by the authors.

Figure 1
Figure 1. Program for computing a polynomial Ppxq of degree n using 4 recursive calls to x, 2n ` 2 basic instructions, and n ` 2 registers 6 [PITH_FULL_IMAGE:figures/full_fig_p007_1.png] view at source ↗

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

  1. Linear Matroid Intersection is in Catalytic Logspace

    cs.CC 2025-09 conditional novelty 7.0 of 10

    Linear matroid intersection is solvable in catalytic logspace with polynomial time, the hardest problem yet known to lie in the class CL.

Reference graph

Works this paper leans on

46 extracted references · 41 canonical work pages · cited by 1 Pith paper

  1. [1]

    Bipartite matching is in catalytic logspace

    Aryan Agarwala and Ian Mertz. Bipartite matching is in catalytic logspace. In Electron. Colloquium Comput. Complex , volume 48, 2025

    work page 2025

  2. [2]

    Representations of multivariate polynomials by sums of univariate polynomials in linear forms

    Andrzej Bia ynicki-Birula and Andrzej Schinzel. Representations of multivariate polynomials by sums of univariate polynomials in linear forms. In Colloquium Mathematicum , volume 2, pages 201--233, 2008

    work page 2008

  3. [3]

    Computing algebraic formulas using a constant number of registers

    Michael Ben - Or and Richard Cleve. Computing algebraic formulas using a constant number of registers. SIAM J. Comput. , 21(1):54--58, 1992

    work page 1992

  4. [4]

    Cook, Patrick W

    Allan Borodin, Stephen A. Cook, Patrick W. Dymond, Walter L. Ruzzo, and Martin Tompa. Two applications of inductive counting for complementation problems. SIAM J. Comput. , 18(3):559--578, 1989

    work page 1989

  5. [5]

    Computing with a full memory: catalytic space

    Harry Buhrman, Richard Cleve, Michal Kouck \`y , Bruno Loff, and Florian Speelman. Computing with a full memory: catalytic space. In Proceedings of the forty-sixth annual ACM symposium on Theory of computing , pages 857--866, 2014

    work page 2014

  6. [6]

    Parallel computation for well-endowed rings and space-bounded probabilistic machines

    Allan Borodin, Stephen Cook, and Nicholas Pippenger. Parallel computation for well-endowed rings and space-bounded probabilistic machines. Information and control , 58(1-3):113--136, 1983

    work page 1983

  7. [7]

    Almost-catalytic computation

    Sagar Bisoyi, Krishnamoorthy Dinesh, Bhabya Deep Rai, and Jayalal Sarma. Almost-catalytic computation. arXiv preprint arXiv:2409.07208 , 2024

    arXiv 2024

  8. [8]

    On pure space vs catalytic space

    Sagar Bisoyi, Krishnamoorthy Dinesh, and Jayalal Sarma. On pure space vs catalytic space. Theoretical Computer Science , 921:112--126, 2022

    work page 2022

Show all 46 references
  1. [9]

    The polynomial method in circuit complexity

    Richard Beigel. The polynomial method in circuit complexity. In [1993] Proceedings of the Eigth Annual Structure in Complexity Theory Conference , pages 82--95. IEEE, 1993

    1993

  2. [10]

    Catalytic space: Non-determinism and hierarchy

    Harry Buhrman, Michal Kouck \`y , Bruno Loff, and Florian Speelman. Catalytic space: Non-determinism and hierarchy. Theory of Computing Systems , 62:116--135, 2018

    2018

  3. [11]

    On relating time and space to size and depth

    Allan Borodin. On relating time and space to size and depth. SIAM journal on computing , 6(4):733--744, 1977

    1977

  4. [12]

    Generators for certain alternating groups with applications to cryptography

    Don Coppersmith and Edna Grossman. Generators for certain alternating groups with applications to cryptography. SIAM Journal on Applied Mathematics , 29(4):624--627, 1975

    1975

  5. [13]

    Computing algebraic formulas with a constant number of registers

    Richard Cleve. Computing algebraic formulas with a constant number of registers. In Proceedings of the twentieth annual ACM symposium on Theory of computing , pages 254--257, 1988

    1988

  6. [14]

    Methodologies for designing block ciphers and cryptographic protocols

    Richard Erwin Cleve. Methodologies for designing block ciphers and cryptographic protocols . PhD thesis, University of Toronto, 1990

    1990

  7. [15]

    The structure of catalytic space: Capturing randomness and time via compression

    James Cook, Jiatu Li, Ian Mertz, and Edward Pyne. The structure of catalytic space: Capturing randomness and time via compression. ECCC TR24-106, 2024

    2024

  8. [16]

    Catalytic approaches to the tree evaluation problem

    James Cook and Ian Mertz. Catalytic approaches to the tree evaluation problem. In Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing , pages 752--760, 2020

    2020

  9. [17]

    Encodings and the tree evaluation problem

    James Cook and Ian Mertz. Encodings and the tree evaluation problem. In Electron. Colloquium Comput. Complex , volume 54, 2021

    2021

  10. [18]

    Trading time and space in catalytic branching programs

    James Cook and Ian Mertz. Trading time and space in catalytic branching programs. In 37th Computational Complexity Conference (CCC 2022) . Schloss-Dagstuhl-Leibniz Zentrum f \"u r Informatik, 2022

    2022

  11. [19]

    Tree evaluation is in space o (log n log log n)

    James Cook and Ian Mertz. Tree evaluation is in space o (log n log log n). In Electron. Colloquium Comput. Complex. , 2023

    2023

  12. [20]

    Pebbles and branching programs for tree evaluation

    Stephen Cook, Pierre McKenzie, Dustin Wehr, Mark Braverman, and Rahul Santhanam. Pebbles and branching programs for tree evaluation. ACM Transactions on Computation Theory (TOCT) , 3(2):1--43, 2012

    2012

  13. [21]

    The classification of problems which have fast parallel algorithms

    Stephen A Cook. The classification of problems which have fast parallel algorithms. In International Conference on Fundamentals of Computation Theory , pages 78--93. Springer, 1983

    1983

  14. [22]

    Randomized and symmetric catalytic computation

    Samir Datta, Chetan Gupta, Rahul Jain, Vimal Raj Sharma, and Raghunath Tewari. Randomized and symmetric catalytic computation. In International Computer Science Symposium in Russia , pages 211--223. Springer, 2020

    2020

  15. [23]

    Opening up the distinguisher: A hardness to randomness approach for bpl= l that uses properties of bpl

    Dean Doron, Edward Pyne, and Roei Tell. Opening up the distinguisher: A hardness to randomness approach for bpl= l that uses properties of bpl. In Proceedings of the 56th Annual ACM Symposium on Theory of Computing , pages 2039--2049, 2024

    2024

  16. [24]

    Hardness of function composition for semantic read once branching programs

    Jeff Edmonds, Venkatesh Medabalimi, and Toniann Pitassi. Hardness of function composition for semantic read once branching programs. In 33rd Computational Complexity Conference (CCC 2018) . Schloss-Dagstuhl-Leibniz Zentrum f \"u r Informatik, 2018

    2018

  17. [25]

    Fully characterizing lossy catalytic computation

    Marten Folkertsma, Ian Mertz, Florian Speelman, and Quinten Tupker. Fully characterizing lossy catalytic computation. arXiv preprint arXiv:2409.05046 , 2024

    2024 arXiv

  18. [26]

    Unambiguous catalytic computation

    Chetan Gupta, Rahul Jain, Vimal Raj Sharma, and Raghunath Tewari. Unambiguous catalytic computation. In 39th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2019) . Schloss-Dagstuhl-Leibniz Zentrum f \"u r Informatik, 2019

    2019

  19. [27]

    Lossy catalytic computation

    Chetan Gupta, Rahul Jain, Vimal Raj Sharma, and Raghunath Tewari. Lossy catalytic computation. arXiv preprint arXiv:2408.14670 , 2024

    2024 arXiv

  20. [28]

    Solving tree evaluation in o (log n log log n) space

    Oded Goldreich. Solving tree evaluation in o (log n log log n) space. ECCC, TR24-124 , 2024

    2024

  21. [29]

    Read-once branching programs for tree evaluation problems

    Kazuo Iwama and Atsuki Nagao. Read-once branching programs for tree evaluation problems. ACM Transactions on Computation Theory (TOCT) , 11(1):1--12, 2018

    2018

  22. [30]

    Catalytic computation

    Michal Kouck \`y et al. Catalytic computation. Bulletin of EATCS , 1(118), 2016

    2016

  23. [31]

    Collapsing catalytic classes

    Michal Kouck\' y , Ian Mertz, Ted Pyne, and Sasha Sami. Collapsing catalytic classes. In Electron. Colloquium Comput. Complex , volume 19, 2025

    2025

  24. [32]

    Pebbling arguments for tree evaluation

    David Liu. Pebbling arguments for tree evaluation. arXiv preprint arXiv:1311.0293 , 2013

    2013 arXiv

  25. [33]

    Distinguishing, predicting, and certifying: On the long reach of partial notions of pseudorandomness

    Jiatu Li, Edward Pyne, and Roei Tell. Distinguishing, predicting, and certifying: On the long reach of partial notions of pseudorandomness. In 2024 IEEE 65th Annual Symposium on Foundations of Computer Science (FOCS) , pages 1--13. IEEE, 2024

    2024

  26. [34]

    Catalytic computing, tree evaluation, & clean computation, 2020

    Ian Mertz. Catalytic computing, tree evaluation, & clean computation, 2020

    2020

  27. [35]

    Reusing space: Techniques and open problems

    Ian Mertz. Reusing space: Techniques and open problems. Bulletin of EATCS , 141(3), 2023

    2023

  28. [36]

    On simultaneous resource bounds

    Nicholas Pippenger. On simultaneous resource bounds. In 20th Annual Symposium on Foundations of Computer Science (sfcs 1979) , pages 307--311. IEEE, 1979

    1979

  29. [37]

    A note on amortized branching program complexity

    Aaron Potechin. A note on amortized branching program complexity. arXiv preprint arXiv:1611.06632 , 2016

    2016 arXiv

  30. [38]

    Sheffield, and William Wang

    Edward Pyne, Nathan S. Sheffield, and William Wang. Catalytic Communication . In Raghu Meka, editor, 16th Innovations in Theoretical Computer Science Conference (ITCS 2025) , volume 325 of Leibniz International Proceedings in Informatics (LIPIcs) , pages 79:1--79:24, Dagstuhl,...

    2025

  31. [39]

    Derandomizing logspace with a small shared hard drive

    Edward Pyne. Derandomizing logspace with a small shared hard drive. In 39th Computational Complexity Conference (CCC 2024) . Schloss Dagstuhl--Leibniz-Zentrum f \"u r Informatik, 2024

    2024

  32. [40]

    On uniform circuit complexity

    Walter L Ruzzo. On uniform circuit complexity. Journal of Computer and System Sciences , 22(3):365--383, 1981

    1981

  33. [41]

    Amortized circuit complexity, formal complexity measures, and catalytic algorithms

    Robert Robere and Jeroen Zuiddam. Amortized circuit complexity, formal complexity measures, and catalytic algorithms. In 2021 IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS) , pages 759--769. IEEE, 2022

    2021

  34. [42]

    On a decomposition of polynomials in several variables

    Andrzej Schinzel. On a decomposition of polynomials in several variables. Journal de th \'e orie des nombres de Bordeaux , 14(2):647--666, 2002

    2002

  35. [43]

    The synthesis of two-terminal switching circuits

    Claude E Shannon. The synthesis of two-terminal switching circuits. The Bell System Technical Journal , 28(1):59--98, 1949

    1949

  36. [44]

    Circuit definitions of nondeterministic complexity classes

    H Venkateswaran. Circuit definitions of nondeterministic complexity classes. SIAM Journal on Computing , 21(4):655--670, 1992

    1992

  37. [45]

    Introduction to circuit complexity: a uniform approach

    Heribert Vollmer. Introduction to circuit complexity: a uniform approach . Springer Science & Business Media, 1999

    1999

  38. [46]

    Simulating time with square-root space

    Ryan Williams. Simulating time with square-root space. In Proceedings of the nineteenth annual ACM symposium on Theory of computing , 2025

    2025

Pith tools

Reviewed August 16, 2026 · model on record in the stance chip above.