alt Hacker NewsWait but if "bits of memory" here was supposed to be "units of computation", that means that:
* The old assumption was that if you require t steps to complete, you need t/log(t) units of computation
* This new proof shows that if you require t steps to complete, you need sqrt(t) units of computation
Surely this doesn't make sense? Using any definition of "unit of computation" I would intuitively assume, computing t steps requires something proportionalt to t units of computation...
There is a bit of nuances here that is difficult to explain fully but note from the paper.
> Our simulation reduces the problem of simulating time-bounded multitape Turing machines to a series of implicitly-defined Tree Evaluation instances with nice parameters, leveraging the remarkable space-efficient algorithm for Tree Evaluation recently found by Cook and Mertz [STOC 2024].
The "time-bounded multitape Turing machines" with bounded fan-in means that that particular abstract model has access to the bits of those tapes current head position.
Mapping the quirks of the various abstract models can be tricky, but remember having access to the symbol currently under the tape head is 'free' in TMs.
It is a useful abstraction but doesn't directly map to physically realizable machine.
It is still an interesting result for trees in physically realizable machines.