Revolutionary Breakthrough: How Space Can Be Squeezed Into Time by Computer Scientist 🕰️

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: https://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 — https://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 — https://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 — https://arxiv.org/abs/1005.2642 (research paper)

You Need Much Less Memory than Time, Lance Fortnow — https://blog.computationalcomplexity.org/2025/02/you-need-much-less-memory-than-time.html (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 — https://iuuk.mff.cuni.cz/~iwmertz/papers/m23.reusing_space.pdf (survey article / notes)

Simulating Time with Square-Root Space, Ryan Williams — https://www.youtube.com/watch?v=1qwDO5ulUFs (recorded talk)

The Tree Evaluation Problem: Context and Recent Results, Ian Mertz — https://www.youtube.com/watch?v=_KEORzRpxY8 (recorded talk)

Catalytic Computing Taps the Full Power of a Full Hard Drive, Quanta Magazine — https://www.quantamagazine.org/catalytic-computing-taps-the-full-power-of-a-full-hard-drive-20250218 (popular article)

A Turing Machine — https://www.youtube.com/watch?v=E3keLeMwfHY (video with physical implementation of Turing machine)

_______________

Created by Kelsey Houston-Edwards
Website: https://www.kelseyhoustonedwards.com