[gracenotes]

Nice article. I got too far into it before realizing I was essentially tricked into reading an academic paper :) There seems to be a tradeoff between clear presentation of an idea and the formalization required to usefully build off of it/publish it. Abstractions which do both (e.g. Turing machines) get more reuse, I think.

The sublogarithmic result is constructive, though, and my understanding of it is like this: We can split up a decision problem (take in a string, give a yes/no answer) over many workers by splitting up the input string into sqrt(n) chunks of size sqrt(n) each and using a shared working space. The first worker handles the first chunk with a blank working space, the second worker handles the second chunk with finished working space from the first one, etc. until the last worker handles the last chunk, with the second-to-last's working space, and gives a yes/no answer. This can be parallelized into a single MapReduce round by instead having every worker process their chunk using every possible configuration of the shared working tape. This sounds like a lot of work, but if shared working area is sublogarithmic in size, calculating such a table fits within polynomial time and sqrt(n) space. This means that one final "reduce" step can take the working space from the first input chunk, pass it through the second input chunk in constant time, and so on until it can make a decision.

I can't think of any practical sublogarithmic space problems off the top of my head but evidently there are some good ones in graph theory. If you tried to implement the above in practice, you could imagine that the final reduce step could be intelligent about combining the processing stages so workers don't need to calculate every single configuration.

What is unclear to me is whether all Turing machine deciding languages in sublogarithmic space can be chunked in this way. The usual definition of an input read head is that you can go left or right whenever you want, but having access to the entire input means that the workers can't be cleanly chunked. You could say the input is one-way like a DFA/PDA, but is there a result that these are equivalent with sublogarithmic scratch space?