One Pebble Versus ϵ · log n Bits
Viliam Geffert, Giovanni Pighizzini, Carlo Mereghetti · Fundamenta Informaticae · 2010
We show that, for any ϵ > 0, there exists a language accepted in strong ϵ log n space by a 2-way deterministic Turing machine working with a single binary worktape, that cannot be accepted in sublogarithmic weak space by any pebble machine (i.e.,