Compressed timestamps and efficient random walks in catalytic space

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.