Time-Space Tradeoff In Derandomizing Probabilistic Logspace Download as PS


Abstract

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.5 n). However, their simulation runs in time nΘ(log0.5n). We prove a time-space tradeoff that interpolates these two simulations. Specifically, we prove that, for any 0 ≤ a ≤ 0.5, any randomized logarithmic space algorithm (running in polynomial time and with two-sided error) can be simulated deterministically in time nO(log0.5-an) and space O(log1.5+an).


dieter@cs.wisc.edu