
Catalytic Tree Evaluation from Matching Vectors
Seyoon Ragavan, a researcher at MIT, presents this Institute for Advanced Study Computer Science/Discrete Mathematics seminar on the tree evaluation problem, a key test case for understanding the relative power of time and space in computation. He reviews prior approaches, including the Cook-Mertz algorithm running in slightly super-logarithmic space, and the catalytic-computing model introduced by Buhrman et al., where an algorithm is given a full hard drive it must return unchanged after use. Ragavan then presents his own result, a catalytic algorithm for tree evaluation using logarithmic free space, polynomial time, and only subpolynomial catalytic space, improving on the earlier poly(n) catalytic space bound. The talk's central idea is a connection drawn between private information retrieval and tree evaluation, both reducible to evaluating a function on a masked input. The lecture is blackboard-and-slides mathematics aimed at specialists in complexity theory and space-bounded computation.