Coursera Flash Sale
40% Off Coursera Plus for 3 Months!
Grab it
This computer science seminar presents a breakthrough in computational complexity theory where Ryan Williams from MIT demonstrates how multitape Turing machines running in time t can be simulated in space O(√(t log t)). Learn about this significant improvement over the previous O(t/log t) space bound established by Hopcroft, Paul, and Valiant approximately 50 years ago. Discover the implications of this advancement, including how bounded fan-in circuits of size s can be evaluated in s√⋅poly(log s) space, and how this makes progress on the longstanding P versus PSPACE problem by identifying explicit problems solvable in O(n) space that require essentially n² time on multitape Turing machines. The talk explains how this simulation works by reducing the problem to an implicitly defined Tree Evaluation instance with favorable parameters, building upon Cook and Mertz's space-efficient algorithm for Tree Evaluation from STOC 2024.
