Breakthrough Tracker record
Simulating Time With Square-Root Space
Williams proved that every multitape Turing-machine computation running in time t can be simulated in O(sqrt(t log t)) space. This substantially improves the previous O(t/log t) universal bound.
← Back to the filtered Breakthrough Tracker
- Stable ID
square-root-space-simulation-2025- Revision
square-root-space-simulation-2025.v1- Field
- Computer Science · Computational complexity
- Evidence
- Tier 1 · Peer reviewed: Yes
- Record state
- Current · Verified/accepted conference result
- Last checked
AI role
No AI assistance was disclosed in the paper or linked reporting.
Record details
- Problem or result
- The general relationship between computation time and memory, including the 50-year-old Hopcroft–Paul–Valiant simulation bound
- Authors
- R. Ryan Williams
- Institutions
- Massachusetts Institute of Technology
- Result date
- February 25, 2025; published at STOC 2025
Why it matters
The theorem is the first major improvement in half a century on a foundational time-versus-space simulation.
Limits
It does not prove P is different from PSPACE. Its formal scope is multitape Turing machines and related models, not immediate memory savings for production software.
Sources
- Primary: Final ACM STOC 2025 proceedings record
- Primary: Primary paper on arXiv
- Independent: Quanta Magazine explanation
Correction and revision history
- July 22, 2026 — Added the ACM STOC 2025 version of record; result and status unchanged.
Machine-readable: JSON v1 · CSV v1 · Schema v1
This individual record remains noindex until a story-specific featured image passes Kingy’s rendered-pixel visual review. The source-linked tracker hub remains the public index.