Tree Evaluation and Simulating Time with Space
- LecturerMr. Tyler Besselman (New York University Shanghai)
Host: Kai-Min Chung - Time2025-11-20 (Thu.) 10:15 ~ 12:15
- LocationAuditorium 101 at IIS new Building
Abstract
In this talk, I will explore recent results surrounding a breakthrough advance in simulating time with space on multi-tape Turing machines as first shown in [Wil25]. I will introduce the Tree Evaluation problem [CMWBS10], show the naive algorithm, and then the improved algorithm put forth by Cook and Mertz [CM24] in O(log n loglog n) space. I will explain how Williams uses this algorithm to simulate a time t multi-tape Turing machine in O([@BackSlash]sqrt{ t log t }) space, and conclude by looking at the results of a recent paper by Shalunov [Sha25] that shows how to evaluate circuits of size s in O([@BackSlash]sqrt{ s log s }) space using the same improved Tree Evaluation algorithm.