Time-Space Tradeoff in Derandomizing Probabilistic Logspace.

Nisan showed that any randomized logarithmic space algorithm (running in polynomial time and with two-sided error) can be simulated by a deterministic algorithm that runs simultaneously in polynomial time and Θ(log2 n) space. Subsequently Saks and Zhou improved the space complexity and showed that a deterministic simulation can be carried out in space Θ(log1.5n). However, their simulation runs in time nΘ(log^{0.5}n). We prove a time--space tradeoff that interpolates these two simulations. Specifically, we prove that, for any 0 ≤ α ≤ 0.5, any randomized logarithmic space algorithm (running in polynomial time and with two-sided error) can be simulated deterministically in time nO(log^{0.5-α}n) and space O(log^{1.5+α}n). That is, we prove that BPL ⊆ DTISP[nO(log^{0.5-α}n), O(log1.5+αn)]. [ABSTRACT FROM AUTHOR]