Catalytic Tree Evaluation from Matching Vectors

What is the relative computational power of time and space? Tree evaluation (TreeEval) has become a central problem in understanding this question, especially after its application by Williams (STOC 2025, IAS CSDM seminar 9/23/25) to prove a landmark result on simulating time with square root space.

One existing approach to solving TreeEval in low space is the algorithm by J. Cook and Mertz (STOC 2024) running in slightly super-logarithmic space O(log n log log n) and super-polynomial time n^{O(log log n)}. Another approach starts by considering a twist on the low-space model known as the catalytic-computing model: the algorithm is also given a large hard drive (catalytic space) that is already full, and can use this hard drive as long as it is ultimately returned to its initial state. In this model, Buhrman et al. (STOC 2014) gave a catalytic algorithm for TreeEval running in logarithmic O(log n) free space and poly(n) time, but with catalytic space also poly(n).

I will show that the latter result can be improved. Our work gives a catalytic algorithm for TreeEval with O(log n) free space, poly(n) time, and subpolynomial catalytic space 2^{log^epsilon n} (for any epsilon > 0). Our result opens a new line of attack on putting TreeEval in logspace, and immediately implies an improved simulation of time by catalytic space via the aforementioned reduction of Williams.

The most important message of my talk will be the connection we drew between private information retrieval (Kopparty, IAS CSDM seminar 3/31/25) and TreeEval to arrive at this result. The crux of both problems is to evaluate some function on a masked input. In catalytic computing, the mask comes from the initial contents of the catalytic hard drive; in private information retrieval, the mask is sampled randomly by the client to ensure privacy. I will not assume any prior knowledge of catalytic algorithms, tree evaluation, or private information retrieval.

Based on joint work (arXiv:2602.14320) with Alexandra Henzinger (MIT) and Edward Pyne (MIT).