Abstract:

The Tree Evaluation Problem has emerged in the past decade as a leading candidate for separating logspace from polynomial time. In this talk we will introduce the problem as well as the context behind its introduction and conjectured hardness. Then we review recent lines of work---including an upcoming result of Cook and Mertz---challenging this conjecture, and discuss their potential for space-bounded algorithms at large.