pith. sign in

arxiv: 2605.09648 · v1 · submitted 2026-05-10 · 💻 cs.CC

Understanding Robust Catalytic Computing

Michal Kouck\'y , Ian Mertz , Sasha Sami This is my paper

Pith reviewed 2026-05-12 02:14 UTC · model grok-4.3

classification 💻 cs.CC
keywords catalytic computinglossy catalytic computingspace complexityrobust computationderandomizationlogspacecatalytic spacereset errors
0
0 comments X

The pith

Robust catalytic computing with small reset errors equates to standard complexity classes.

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

The paper introduces three natural relaxations of catalytic computing that allow limited errors when resetting the catalytic tape: randomized models that may destroy the tape with positive probability or incur a bounded number of errors in expectation, and a deterministic model with bounded expected errors over the initial tape. It proves near-complete characterizations by showing these models are equivalent to one another, to errorless catalytic space, or to ordinary time and space classes, both in general and in the logspace polynomial-time regime. This supports using catalytic techniques more reliably inside space-bounded algorithms without demanding perfect restoration. Under a derandomization assumption the paper shows a near-full collapse of all catalytic classes in the logspace setting.

Core claim

We expand the definition of possible resetting error in three natural ways: randomized catalytic computation which can completely destroy the catalytic tape with some probability over the randomness, randomized catalytic computation which makes a bounded number of errors in expectation over the randomness, and deterministic catalytic computation which makes a bounded number of errors in expectation over the initial catalytic tape itself. We show a near complete characterization of the above models, both in the general case and in the logspace polynomial-time regime, by showing equivalences either between one another, to errorless catalytic space models, or to standard time or space complex

What carries the argument

Three extended models of lossy catalytic computation allowing probabilistic tape destruction, expected errors over randomness, or expected errors over the initial tape content.

If this is right

  • The three robust models are equivalent to errorless catalytic space or to standard time and space classes.
  • In the logspace polynomial-time regime the robust models match known complexity classes.
  • Under the derandomization assumption nearly all existing catalytic classes collapse into one another.
  • Catalytic techniques can be applied robustly inside space-bounded algorithms without changing the underlying complexity.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The equivalences imply that modest robustness requirements do not enlarge the power of catalytic space in either the general or logspace setting.
  • The collapse result may link to open questions about derandomizing space-bounded computation more broadly.
  • The characterizations could be tested by checking whether known separating problems between related classes also separate any of the robust variants unconditionally.

Load-bearing premise

The derandomization assumption required to obtain the near-full collapse of catalytic classes in the logspace polynomial-time regime.

What would settle it

An explicit separation in the logspace polynomial-time regime between one of the new robust models and either the errorless catalytic class or a standard time-space class, or a counterexample to any of the claimed equivalences that holds unconditionally.

Figures

Figures reproduced from arXiv: 2605.09648 by Ian Mertz, Michal Kouck\'y, Sasha Sami.

Figure 1
Figure 1. Figure 1: Basic class structure for logspace catalytic classes. Color coding: black = old classes; green + rectangle = robust catalytic classes introduced in this work; blue = reference classes which were implicitly previously defined but which have not been previously studied. Upwards lines indicate known or definitional inclusions. 1.4 Open questions The main gap in our results is to show that BPϵC δ Llow and ERan… view at source ↗
Figure 2
Figure 2. Figure 2: Summary of results (all green equalities and containments). In the unconditional setting, all new classes are either 1) equal to a preexisting class; 2) find themselves in two new clusters (note that ≈ means the parameters are not tight enough for full equality); or 3) are one of two stray classes. In the conditional setting, almost all new classes collapse to CL and all classes are comparable with the sol… view at source ↗
Figure 3
Figure 3. Figure 3: Catalytic tape To prove Theorem 49, we describe a deterministic catalytic algorithm B, which always resets the tape and decides the language L. B has the following catalytic tape structure: it consists of c bits denoted by τ in [PITH_FULL_IMAGE:figures/full_fig_p030_3.png] view at source ↗
Figure 4
Figure 4. Figure 4: Catalytic tape The hash functions on the catalytic tape are derived from a 2-independent hash family H = {h : {0, 1} m → {0, 1} m} with a size of 2 2m, as in Nisan’s PRG [Nis92]; where each hash function can be computed in O(m) space. B.1 The parameters The parameters of interest are: • m the seed length of the PRGs that will be built, which we will set later. We can think of m = d · s, for a large constan… view at source ↗
read the original abstract

Catalytic computing concerns space bounded computation which starts with memory full of data that have to be restored by the end of the computation. Lossy catalytic computing, defined by Gupta et al. (2024) and fully characterized by Folkertsma et al. (ITCS 2025), is the study of allowing a small number of errors when resetting the catalytic tape at the end of a computation. Such a notion is useful when considering the robust use of catalytic techniques in the study of ordinary space-bounded algorithms. To that end however, defining and characterizing less strict notions of error was left open by Folkertsma et al. (ITCS 2025) and other works such as Mertz (B. EATCS, 2023). We expand the definition of possible resetting error in three natural ways: 1. randomized catalytic computation which can completely destroy the catalytic tape with some probability over the randomness 2. randomized catalytic computation which makes a bounded number of errors in expectation over the randomness 3. deterministic catalytic computation which makes a bounded number of errors in expectation over the initial catalytic tape itself We show a near complete characterization of the above models, both in the general case and in the logspace polynomial-time regime, by showing equivalences either between one another, to errorless catalytic space models, or to standard time or space complexity classes. Under a derandomization assumption, we show a near full collapse of all existing catalytic classes in the logspace regime.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

1 major / 2 minor

Summary. The paper expands the definition of resetting error in catalytic computing in three natural ways: (1) randomized catalytic computation that may completely destroy the catalytic tape with positive probability, (2) randomized catalytic computation making a bounded number of errors in expectation, and (3) deterministic catalytic computation making a bounded number of errors in expectation over the initial catalytic tape. It claims near-complete characterizations of these models in both the general case and the logspace polynomial-time regime, via equivalences among the models, to errorless catalytic space models, or to standard time/space complexity classes. Under a derandomization assumption, it further claims a near-full collapse of all existing catalytic classes in the logspace regime.

Significance. If the claimed equivalences and characterizations hold, the work provides a systematic unification of robust catalytic models that clarifies their relationships to each other and to classical classes, which is useful for applying catalytic techniques in space-bounded algorithms. The unconditional results are particularly valuable as they offer clean inter-reductions without additional assumptions. The conditional collapse result connects catalytic computing to derandomization questions, but its significance depends on the precise strength of the invoked assumption; a mild assumption would make the collapse more impactful. Overall, the paper strengthens the foundations of catalytic space complexity.

major comments (1)
  1. [Abstract and the section presenting the logspace collapse] The derandomization assumption used to obtain the near-full collapse of catalytic classes in the logspace polynomial-time regime is not explicitly defined or compared to existing hypotheses (such as space-bounded PRGs or derandomization of BPL). This assumption is load-bearing for the conditional claim in the abstract and the corresponding theorem.
minor comments (2)
  1. [Abstract] The abstract uses the qualifiers 'near complete' and 'near full' without specifying which classes are included or excluded in the characterizations and collapse; this should be clarified for precision.
  2. [Preliminaries] Notation and definitions for the three error models could be introduced with a summary table or diagram in the preliminaries to improve readability across the general and logspace cases.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for their careful reading, positive overall assessment, and constructive feedback on our manuscript. We address the single major comment below and will revise the paper accordingly to improve clarity.

read point-by-point responses

  1. Referee: [Abstract and the section presenting the logspace collapse] The derandomization assumption used to obtain the near-full collapse of catalytic classes in the logspace polynomial-time regime is not explicitly defined or compared to existing hypotheses (such as space-bounded PRGs or derandomization of BPL). This assumption is load-bearing for the conditional claim in the abstract and the corresponding theorem.

    Authors: We agree that the assumption should be stated more explicitly for the benefit of readers. In the revised version we will (i) give a precise definition of the derandomization hypothesis in both the abstract and the relevant theorem statement, (ii) compare its strength to standard hypotheses such as the existence of space-bounded pseudorandom generators and the derandomization of BPL, and (iii) briefly discuss why the hypothesis is mild in the context of catalytic space. These additions will make the conditional collapse result easier to evaluate without altering any technical claims. revision: yes

Circularity Check

0 steps flagged

No circularity; equivalences are explicit reductions to prior models and standard classes

full rationale

The paper introduces three new error models for robust catalytic computation and claims to establish equivalences via direct reductions to each other, to errorless catalytic space, or to standard time/space classes. These are presented as proven characterizations rather than self-definitions, fitted parameters renamed as predictions, or ansatzes smuggled via citation. The derandomization assumption for the logspace collapse is invoked as an external hypothesis without being derived from the paper's own constructions. Self-citations (e.g., to Mertz 2023) serve only as background for the open problem and are not load-bearing for the new equivalences or uniqueness claims. The derivation chain consists of standard complexity-theoretic arguments that remain independent of the target results.

Axiom & Free-Parameter Ledger

0 free parameters · 0 axioms · 0 invented entities

Abstract-only review; no free parameters, axioms, or invented entities are mentioned or needed for the high-level claims.

pith-pipeline@v0.9.0 · 5568 in / 1206 out tokens · 51008 ms · 2026-05-12T02:14:16.438479+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

  • IndisputableMonolith/Foundation/RealityFromDistinction.lean reality_from_one_distinction unclear
    ?
    unclear

    Relation between the paper passage and the cited Recognition theorem.

    We expand the definition of possible resetting error in three natural ways: 1. randomized catalytic computation which can completely destroy the catalytic tape with some probability... 2. ...in expectation over the randomness 3. deterministic...over the initial catalytic tape itself. We show a near complete characterization... Under a derandomization assumption, we show a near full collapse...

  • IndisputableMonolith/Cost/FunctionalEquation.lean washburn_uniqueness_aczel unclear
    ?
    unclear

    Relation between the paper passage and the cited Recognition theorem.

    Configuration graphs... τβ-graph... compress-or-random... Nisan’s pseudo-random generator... PRGs under Conjecture 43

What do these tags mean?
matches
The paper's claim is directly supported by a theorem in the formal canon.
supports
The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends
The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses
The paper appears to rely on the theorem as machinery.
contradicts
The paper's claim conflicts with a theorem or certificate in the canon.
unclear
Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.

Reference graph

Works this paper leans on

210 extracted references · 210 canonical work pages

  1. [1]

    Catalytic Coherence , author =. Phys. Rev. Lett. , volume =. 2014 , month =

    work page 2014

  2. [2]

    2026 , doi =

    Aryan Agarwala and Yaroslav Alekseev and Antoine Vinciguerra , title =. 2026 , doi =

    work page 2026

  3. [3]

    Aryan Agarwala and Ian Mertz , title =

    work page

  4. [4]

    Ryan Williams , title =

    Shyan Akmal and R. Ryan Williams , title =. 2021 , doi =

    work page 2021

  5. [5]

    Buss and Shlomo Moran and Toniann Pitassi , title =

    Michael Alekhnovich and Samuel R. Buss and Shlomo Moran and Toniann Pitassi , title =

    work page

  6. [6]

    Razborov , title =

    Michael Alekhnovich and Alexander A. Razborov , title =

    work page

  7. [7]

    2025 , doi =

    Yaroslav Alekseev and Yuval Filmus and Ian Mertz and Alexander Smal and Antoine Vinciguerra , title =. 2025 , doi =

    work page 2025

  8. [8]

    2023 , doi =

    Eric Allender , title =. 2023 , doi =

    work page 2023

  9. [9]

    Eric Allender and Anna G. Dual

    work page

  10. [10]

    Vinay , title =

    Eric Allender and Jia Jiao and Meena Mahajan and V. Vinay , title =. 1998 , doi =

    work page 1998

  11. [11]

    Eric Allender and Klaus Reinhardt and Shiyu Zhou , title =

    work page

  12. [12]

    Simple Construction of Almost k-wise Independent Random Variables , journal =

    Noga Alon and Oded Goldreich and Johan H. Simple Construction of Almost k-wise Independent Random Variables , journal =

    work page

  13. [13]

    Annals of Mathematics , number =

    Ryan Alweiss and Shachar Lovett and Kewen Wu and Jiapeng Zhang , title =. Annals of Mathematics , number =. 2021 , doi =

    work page 2021

  14. [14]

    2009 , isbn =

    Sanjeev Arora and Boaz Barak , title =. 2009 , isbn =

    work page 2009

  15. [15]

    Cliff Liu and Robert E

    Sepehr Assadi and S. Cliff Liu and Robert E. Tarjan , title =. 2021 , pages =

    work page 2021

  16. [16]

    A combinatorial characterization of resolution width , journal = JCSS, volume =

    Albert Atserias and V. A combinatorial characterization of resolution width , journal = JCSS, volume =

    work page

  17. [17]

    2023 , doi =

    Albert Atserias and Massimo Lauria , title =. 2023 , doi =

    work page 2023

  18. [18]

    Narrow Proofs May Be Maximally Long , journal = TOCL, volume =

    Albert Atserias and Massimo Lauria and Jakob Nordstr. Narrow Proofs May Be Maximally Long , journal = TOCL, volume =

    work page

  19. [19]

    Automating Resolution is NP-Hard , journal = JACM, volume =

    Albert Atserias and Moritz M. Automating Resolution is NP-Hard , journal = JACM, volume =

    work page

  20. [20]

    Signed-Digit Number Representations for Fast Parallel Arithmetic , year=

    Avizienis, Algirdas , journal=. Signed-Digit Number Representations for Fast Parallel Arithmetic , year=

    work page

  21. [21]

    A lift-and-project cutting plane algorithm for mixed 0-1 programs , journal =

    Egon Balas and Sebasti. A lift-and-project cutting plane algorithm for mixed 0-1 programs , journal =

    work page

  22. [22]

    Buss and Walter L

    Greg Barnes and Jonathan F. Buss and Walter L. Ruzzo and Baruch Schieber , title =. 1998 , doi =

    work page 1998

  23. [23]

    Mix Barrington , title =

    David A. Mix Barrington , title =. 1989 , doi =

    work page 1989

  24. [24]

    Automating Regular or Ordered Resolution is NP-Hard , journal = ECCC, pages =

    Zo. Automating Regular or Ordered Resolution is NP-Hard , journal = ECCC, pages =

    work page

  25. [25]

    Tolson Bell and Suchakree Chueluecha and Lutz Warnke , title =. Discret. Math. , volume =

    work page

  26. [26]

    Computing Algebraic Formulas Using a Constant Number of Registers , journal = SICOMP, volume =

    Michael Ben. Computing Algebraic Formulas Using a Constant Number of Registers , journal = SICOMP, volume =. doi:10.1137/0221006 , year =

    work page doi:10.1137/0221006

  27. [27]

    Short proofs are narrow - resolution made simple , journal = JACM, volume =

    Eli Ben. Short proofs are narrow - resolution made simple , journal = JACM, volume =

    work page

  28. [28]

    Berlekamp , title =

    Elwyn R. Berlekamp , title =. Symposium on Symbolic and Algebraic Manipulation (SYMSAC) , pages =. 1971 , doi =

    work page 1971

  29. [29]

    Berkowitz , title =

    Stuart J. Berkowitz , title =. 1984 , doi =

    work page 1984

  30. [30]

    doi:10.1016/J.TCS.2022.04.005 , year =

    Sagar Bisoyi and Krishnamoorthy Dinesh and Jayalal Sarma , title =. doi:10.1016/J.TCS.2022.04.005 , year =

    work page doi:10.1016/j.tcs.2022.04.005 2022

  31. [31]

    2025 , doi =

    Sagar Bisoyi and Krishnamoothy Dinesh and Bhabya Rai and Jayalal Sarma , title =. 2025 , doi =

    work page 2025

  32. [32]

    Non-Automatizability of Bounded-Depth Frege Proofs , journal = CC, volume =

    Maria Luisa Bonet and Carlos Domingo and Ricard Gavald. Non-Automatizability of Bounded-Depth Frege Proofs , journal = CC, volume =

    work page

  33. [33]

    Maria Luisa Bonet and Juan Luis Esteban and Nicola Galesi and Jan Johannsen , title =

    work page

  34. [34]

    Maria Luisa Bonet and Toniann Pitassi and Ran Raz , title =

    work page

  35. [35]

    Cook and Nicholas Pippenger , title =

    Allan Borodin and Stephen A. Cook and Nicholas Pippenger , title =. 1983 , doi =

    work page 1983

  36. [36]

    1960 , publisher =

    On a class of error correcting binary group codes , author =. 1960 , publisher =

    work page 1960

  37. [37]

    Cook and Pierre McKenzie and Rahul Santhanam and Dustin Wehr , title =

    Mark Braverman and Stephen A. Cook and Pierre McKenzie and Rahul Santhanam and Dustin Wehr , title =

    work page

  38. [38]

    , title =

    Harry Buhrman and Richard Cleve and Michal Kouck. Computing with a full memory: catalytic space , booktitle = STOC, pages =. doi:10.1145/2591796.2591874 , year =

    work page doi:10.1145/2591796.2591874

  39. [39]

    2016 , howpublished =

    Harry Buhrman and Yfke Dulek and Bruno Loff and Florian Speelman , title =. 2016 , howpublished =

    work page 2016

  40. [40]

    2025 , doi =

    Harry Buhrman and Marten Folkertsma and Ian Mertz and Florian Speelman and Sergii Strelchuk and Sathyawageeswar Subramanian and Quinten Tupker , title =. 2025 , doi =

    work page 2025

  41. [41]

    Catalytic Space: Non-determinism and Hierarchy , journal = TOCS, volume =

    Harry Buhrman and Michal Kouck. Catalytic Space: Non-determinism and Hierarchy , journal = TOCS, volume =. doi:10.1007/S00224-017-9784-7 , year =

    work page doi:10.1007/s00224-017-9784-7

  42. [42]

    Mathematics of Computation , volume =

    James R Bunch and John E Hopcroft , title =. Mathematics of Computation , volume =

    work page

  43. [43]

    Bruno Pasqualotto Cavalar and Mrinal Kumar and Benjamin Rossman , title =

    work page

  44. [44]

    Space-Optimal Quasi-Gray Codes with Logarithmic Read Complexity , booktitle = ESA, series = LIPICS, volume =

    Diptarka Chakraborty and Debarati Das and Michal Kouck. Space-Optimal Quasi-Gray Codes with Logarithmic Read Complexity , booktitle = ESA, series = LIPICS, volume =

    work page

  45. [45]

    Parinya Chalermsook and Marek Cygan and Guy Kortsarz and Bundit Laekhanukit and Pasin Manurangsi and Danupon Nanongkai and Luca Trevisan , title =

    work page

  46. [46]

    Lee and Prasad Raghavendra and David Steurer , title =

    Siu On Chan and James R. Lee and Prasad Raghavendra and David Steurer , title =

    work page

  47. [47]

    Chan and J

    Timothy M. Chan and J. Ian Munro and Venkatesh Raman , title =. 2018 , doi =

    work page 2018

  48. [48]

    doi:10.1137/19M1310153 , year =

    Arkadev Chattopadhyay and Yuval Filmus and Sajin Koroth and Or Meir and Toniann Pitassi , title =. doi:10.1137/19M1310153 , year =

    work page doi:10.1137/19m1310153

  49. [49]

    Simulation Theorems via Pseudo-random Properties , journal = CC, volume =

    Arkadev Chattopadhyay and Michal Kouck. Simulation Theorems via Pseudo-random Properties , journal = CC, volume =

    work page

  50. [50]

    Yijia Chen and Bingkai Lin , title =

    work page

  51. [51]

    2021 , doi =

    Lijie Chen and Roei Tell , title =. 2021 , doi =

    work page 2021

  52. [52]

    2025 , doi =

    Daoyuan Chen and Simon Meierhans and Maximilian Probst Gutenberg and Thatchaphol Saranurak , title =. 2025 , doi =

    work page 2025

  53. [53]

    Edmonds polytopes and a hierarchy of combinatorial problems , journal =

    Vasek Chv. Edmonds polytopes and a hierarchy of combinatorial problems , journal =

    work page

  54. [54]

    Matthew Clegg and Jeff Edmonds and Russell Impagliazzo , title =

    work page

  55. [55]

    Richard Cleve , title =

    work page

  56. [56]

    Cook , title =

    Stephen A. Cook , title =. Information and Control , volume =. 1985 , doi =

    work page 1985

  57. [57]

    Cook and Collette R

    William J. Cook and Collette R. Coullard and Gy. On the complexity of cutting-plane proofs , journal =

    work page

  58. [58]

    2025 , volume =

    The Structure of In-Place Space-Bounded Computation , author =. 2025 , volume =

    work page 2025

  59. [59]

    Cook and Ravi Kannan and Alexander Schrijver , title =

    William J. Cook and Ravi Kannan and Alexander Schrijver , title =. Math. Program. , volume =

    work page

  60. [60]

    James Cook and Jiatu Li and Ian Mertz and Edward Pyne , title =

    work page

  61. [61]

    Fomin, Daniel Lokshtanov, Fahad Panolan, Saket Saurabh, and Meirav Zehavi

    James Cook and Ian Mertz , title =. doi:10.1145/3357713.3384316 , year =

    work page doi:10.1145/3357713.3384316

  62. [62]

    2021 , url =

    James Cook and Ian Mertz , title =. 2021 , url =

    work page 2021

  63. [63]

    doi:10.4230/LIPIcs.CCC.2022.8 , year =

    James Cook and Ian Mertz , title =. doi:10.4230/LIPIcs.CCC.2022.8 , year =

    work page doi:10.4230/lipics.ccc.2022.8 2022

  64. [64]

    2025 , doi =

    James Cook and Ian Mertz , title =. 2025 , doi =

    work page 2025

  65. [65]

    Cook and Pierre McKenzie and Dustin Wehr and Mark Braverman and Rahul Santhanam , title =

    Stephen A. Cook and Pierre McKenzie and Dustin Wehr and Mark Braverman and Rahul Santhanam , title =. doi:10.1145/2077336.2077337 , year =

    work page doi:10.1145/2077336.2077337

  66. [66]

    2009 , month =

    Branching Programs: Avoiding Barriers , author =. 2009 , month =

    work page 2009

  67. [67]

    2026 , doi =

    James Cook and Edward Pyne , title =. 2026 , doi =

    work page 2026

  68. [68]

    1975 , volume=

    Generators for Certain Alternating Groups with Applications to Cryptography , author=. 1975 , volume=. doi:10.1137/0129051 , pages=

    work page doi:10.1137/0129051 1975

  69. [69]

    Dantchev and S

    Stefan S. Dantchev and S. On Relativisation and Complexity Gap , booktitle =

    work page

  70. [70]

    doi:10.1007/978-3-030-50026-9\_15 , year =

    Samir Datta and Chetan Gupta and Rahul Jain and Vimal Raj Sharma and Raghunath Tewari , title =. doi:10.1007/978-3-030-50026-9\_15 , year =

    work page doi:10.1007/978-3-030-50026-9

  71. [71]

    de Rezende , title =

    Susanna F. de Rezende , title =. Latin and American Algorithms, Graphs and Optimization Symposium (LAGOS) , series =

    work page

  72. [72]

    de Rezende and Mika G

    Susanna F. de Rezende and Mika G. Automating algebraic proof systems is NP-hard , booktitle = STOC, pages =

    work page

  73. [73]

    2020 IEEE 61st Annual Symposium on Foundations of Computer Science (FOCS) , pages =

    Susanna F. de Rezende and Or Meir and Jakob Nordstr. doi:10.1109/FOCS46700.2020.00013 , year =

    work page doi:10.1109/focs46700.2020.00013 2020

  74. [74]

    de Rezende and Or Meir and Jakob Nordstr

    Susanna F. de Rezende and Or Meir and Jakob Nordstr. Lifting with Simple Gadgets and Applications to Circuit and Proof Complexity , booktitle = FOCS, pages =

    work page

  75. [75]

    de Rezende and Jakob Nordstr

    Susanna F. de Rezende and Jakob Nordstr. How Limited Interaction Hinders Real Communication (and What It Means for Proof and Circuit Complexity) , booktitle = FOCS, pages =

    work page

  76. [76]

    Advances in Cryptology - EUROCRYPT 2004 , year =

    Dodis, Yevgeniy and Reyzin, Leonid and Smith, Adam , title =. Advances in Cryptology - EUROCRYPT 2004 , year =

    work page 2004

  77. [77]

    2006 , url =

    Dodis, Yevgeniy and Ostrovsky, Rafail and Reyzin, Leonid and Smith, Adam , title =. 2006 , url =

    work page 2006

  78. [78]

    Dean Doron and Edward Pyne and Roei Tell , title =

    work page

  79. [79]

    Ryan Williams , title =

    Dean Doron and Edward Pyne and Roei Tell and R. Ryan Williams , title =. 2025 , doi =

    work page 2025

  80. [80]

    2023 , doi =

    Dean Doron and Roei Tell , title =. 2023 , doi =

    work page 2023

Showing first 80 references.