Compressed timestamps and efficient random walks in catalytic space @SimonsInstitute
Compressed timestamps and efficient random walks in catalytic space  @SimonsInstitute
Uploaded October 2026 | Updated November 2026, 3 days ago
James Cook (Unaffiliated)
https://simons.berkeley.edu/talks/james-cook-unaffiliated-2026-10-27
Derandomization

Come learn about catalytic space! I will present two results about the class CL (catalytic logspace): algorithms which use only O(log n) ordinary memory, but are additionally given a poly(n)-size tape (the ``catalyst'') which is initialized with arbitrary data which must be restored at the end of the computation.

First, a simple algorithm for simulating random walks on a directed graph (ITCS 2026, with Edward Pyne). The algorithm takes Õ(mT^2/ε) time to estimate the probability a T-step random walk on a graph with m edges ends at a particular node within error ε. The time can be reduced to Õ(mT/ε) if the graph is guaranteed acyclic.

Second, I'll demonstrate an example of the ``compress-or-random'' technique for building catalytic algorithms, by proving that CL∩P = CLP: that is, given both a CL algorithm and a P algorithm for the same problem, we can combine them into a single algorithm that runs in polynomial time while using only catalytic logspace (STOC 2025, with Jiatu Li, Ian Mertz, Edward Pyne). This can be thought of as a kind of derandomization: every CL algorithm already runs in polynomial time if the catalytic tape is initialized randomly; we show how to modify a CL algorithm to always run in polynomial time, if we are also given a P algorithm to use as a fallback for certain unlikely (and compressible) initial tape configurations.
Compressed timestamps and efficient random walks in catalytic spaceRandom unitary circuits with constant spectral gapFrom local discrete curvature notions of graphs to global properties of the underlying spacesProperty (T), sums of square and numerical certificatesA Simple Sub-Polynomial Degree Coboundary ExpanderBipartite matching is in NCDistributional Diffusion ModelsHigh-Dimensional Expansion (HDX) (Part 3)Gap Amplification for Local Hamiltonians with Combinatorial SoundnessLabOS: The AI-XR Co-Scientist That Sees and Works With HumansCoboundary Expansion and Locally Testable Codes (Part 1)Evaluating factuality in long-form generation
Simons Institute for the Theory of Computing |

Compressed timestamps and efficient random walks in catalytic space

SHARE TO X SHARE TO REDDIT SHARE TO FACEBOOK WALLPAPER