Title: The Tree Evaluation Problem: Context and Recent Results
Speaker: Ian Mertz (University of Warwick)
Invited by: Bruno Loff (LASIGE, DM/FCUL)
When: October 06, 2023, 14:00
Where: FCUL, C6.2.33

Video recording: https://youtu.be/_V7v-R1k1kA

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.

Bio: I’m a postdoctoral researcher in the Theory and Foundations Group at the University of Warwick, where I’m fortunate to be working with Igor Carboni Oliveira. Before this I was a graduate student at University of Toronto advised by Toniann Pitassi, and before that I was an undergraduate at Rutgers University. At the moment my research interests mostly include catalytic computing, lifting theorems, arithmetic circuit complexity, and proof complexity.

Note: The entry was updated to include the video recording.

This presentation is supported by the project HOFGA, Grant agreement ID: 101041696, funded by European Reserach Council’s Horizon Europe programme.