Astonishing discovery by computer scientist: how to squeeze space into time

An explanation of Ryan Williams' breakthrough proof showing a surprising connection between space and time complexity using the tree evaluation problem.

This year, computer scientist Ryan Williams showed an astounding connection between space and time. He thought it was too strange to be true. But, it is. It’s about space, time, fundamental constraints, a 50-year-old mystery, and magical pebbles that resolved a $100 bet. Play the pebbling game: chalk-talk-math.github.io/pebble-game/ ** reuploaded to fix audio -- thanks for your patience+support *** minor correction: original tree evaluation paper from 2009, not 2018 (see references below) ________________ Timestamps: 0:00 An earthquake of a result 1:28 Computer of the mind 4:24 Back and forth, back and forth 8:33 Unrolling the tree 13:13 Proof by pebbles 16:54 Spinning the dial _______________ References Simulating Time in Square-Root Space , Ryan Williams — eccc.weizmann.ac.il/report/2025/017/ (research paper) Tree Evaluation is in Space O(log n * log log n), James Cook and Ian Mertz — dl.acm.org/doi/10.1145/3618260.3649664 (research paper) Pebbles and Branching Programs for Tree Evaluation, Stephen Cook, Pierre McKenzie, Dustin Wehr, Mark Braverman, Rahul Santhanam — arxiv.org/abs/1005.2642 (research paper) You Need Much Less Memory than Time, Lance Fortnow — blog.computationalcomplexity.org/2025/02/you-need-much-less-… (blog, with quote about "... an earthquake of a result") Introduction to the Theory of Computation, Michael Sipser (textbook, table of contents is shown) Reusing Space: Techniques and Open Problems, Ian Mertz — iuuk.mff.cuni.cz/~iwmertz/papers/m23.reusing_space.pdf (survey article / notes) Simulating Time with Square-Root Space, Ryan Williams — youtube.com/watch?v=1qwDO5ulUFs (recorded talk) The Tree Evaluation Problem: Context and Recent Results, Ian Mertz — youtube.com/watch?v=_KEORzRpxY8 (recorded talk) Catalytic Computing Taps the Full Power of a Full Hard Drive, Quanta Magazine — quantamagazine.org/catalytic-computing-taps-the-full-power-o… (popular article) A Turing Machine — youtube.com/watch?v=E3keLeMwfHY (video with physical implementation of Turing machine) _______________ Created by Kelsey Houston-Edwards Website: kelseyhoustonedwards.com