Borrowing memory that's being used: catalytic approaches to the Tree Evaluation Problem

I'll be presenting some joint work with Ian Mertz scheduled to appear at STOC 2020. The study of the Tree Evaluation Problem (TEP), introduced by S. Cook et al. (TOCT 2012), is a promising approach to separating L from P. Given a label in [k] at each leaf of a complete binary tree and an explicit function [k]^2 -> [k] for recursively computing the value of each internal node from its children, the problem is to compute the value at the root node. A simple recursive algorithm can solve this using Theta(h log k) memory, where h is the tree height and k is the size of the alphabet. Until now, no better deterministic algorithm was known. We present a new algorithm which uses less memory when k is not too big compared to h, inspired by a surprising result from Burhman et al. about “catalytic space" computation (STOC 2012). Ours is the first algorithm to beat the simple recursive algorithm, and also the first non-trivial approach to proving a deterministic upper bound for TEP.