Tree Evaluation and Simulating Time with Space
- 講者Tyler Besselman 先生 (上海紐約大學)
邀請人：鐘楷閔 - 時間2025-11-20 (Thu.) 10:15 ~ 12:15
- 地點資訊所新館101演講廳
摘要
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.