• Main result: Ryan Williams shows in an upcoming STOC paper that all algorithms can be simulated using considerably less memory than the time of the original algorithm, with DTIME(\(t(n)\)) \(\subseteq\) DSPACE(\(\sqrt{t(n)\log t(n)}\)), which is a vast improvement over the previous best known simulation (DTIME(\(t(n)\)) \(\subseteq\) DSPACE(\(t(n)/\log t(n)\))).
• Proof details: The proof relies on a space-efficient tree evaluation algorithm by James Cook and Ian Mertz. The Turing machine's tapes are split into \(\sqrt{t(n)}\) segments. Williams models acceptance as a circuit with bounded degree and depth \(\sqrt{t(n)}\), using wires to carry segment contents. Cook and Mertz use finite fields to encode segments and show how to compute tree nodes with only \(\sqrt{t(n)}\) space.
• Applications and open questions: The theorem works for multitape Turing machines and oblivious random-access machines. It can be used to compute circuit output with nearly \(\sqrt{s}\) space. It kills a 1986 hardness vs randomness assumption. Open questions include pushing the result to get a simulation in space \(n^\epsilon\) for \(\epsilon<1/2\) to separate P from PSPACE and improving for other models like general random access machines. Reading sections 4 and 5 of Williams' paper gives further consequences and challenges.