The Tree Evaluation Problem: Context and Recent Results - Ian Mertz скачать в хорошем качестве

The Tree Evaluation Problem: Context and Recent Results - Ian Mertz

Computer Science/Discrete Mathematics Seminar I Topic: The Tree Evaluation Problem: Context and Recent Results Speaker: Ian Mertz Affiliation: University of Warwick Date: January 26, 2024 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. We then review recent lines of work challenging this conjecture, leading up to a recent result together with James Cook showing near-logspace algorithms for Tree Evaluation.