Computer Science/Discrete Mathematics Seminar I

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.