In 2009, Mark Braverman and four others (Stephen Cook, Pierre McKenzie, Dustin Wehr, and Rahul Santhanam) introduced the Tree Evaluation Problem with the hope of using it to separate L (logarithmic space) from P (polynomial time): if Tree Evaluation could be proved to require more than logarithmic space, that would imply L≠P.

I will explain why solving this problem ought to require Ω((log n)²) space, how it turned out to need much less than that (so far it's down to O(log n log log n / log log log n)), and the part it plays in Ryan Williams's recent result that a time-T multitape Turing machine can be simulated in Õ(√T) space. Incidentally, I'm owed $50.

Time permitting, I will also talk about the surprising and wonderful world of catalytic space, which inspired the space-efficient Tree Evaluation algorithms.

Based on other people's work, and also on my joint work with Jiatu Li, Ian Mertz, and Ted Pyne.