Tree-eval, catalytic computation, simulating time with square-root space

A series of exciting papers [CM24, Wil25, Sha25] shows how to simulate time t on a multi-tape machine in space about . This simulation was already known for 1-tape machines (did you know?), and it still isn’t known for RAMs (=Time). The result for 2 tapes is significant, as we know less about this model, for example we don’t have strong lower bounds.

The first paper to state this simulation is [Wil25], but a similar simulation follows easily from [CM24], as pointed out in [Sha25]. This is all presented in my book, see Chapter 7. Specifically, [CM24] gives a simulation of what I call word circuits (they don’t talk about word circuits, but tree eval, possibly one reason why this connection wasn’t realized before). Any circuit of size s can be turned into a word circuit of depth s∕b with word size b by dividing the gates into blocks of b. Now apply [CM24] to give a space-efficient simulation. Multitape machines are a special case of circuits by previous simulation (also in my book).

This gives a simulation in space about s^2∕3. A relatively simple transformation of the circuit gets you space [Sha25]. This is all for non-uniform space algorithms; I haven’t thought much what happens for uniform but I don’t see a roadblock.

Returning to [CM24], the term “catalytic computation” is often used but I don’t find it useful.  [CM24] is a brilliant extension of some of my favorite results [Mix89, BC92]. The exposition in my book puts it in this context.

References