Reproducibility and Pseudo-Determinism in Log-Space

Ofer Grossman, Yang P. Liu

A curious property of randomized log-space search algorithms is that their outputs are often longer than their workspace. This leads to the question: how can we reproduce the resul…