- Authors:
J.-Y. Cai, V. Chakaravarthy, and D. van Melkebeek.
- Reference:
Theory of Computing Systems, 39: 189-208, 2006.
Special issue dedicated to papers selected from the
21st International Symposium on Theoretical Aspects of Computer
Science.
- Earlier version:
- J.-Y. Cai, V. Chakaravarthy, and D. van Melkebeek.
Time-Space Tradeoff In Derandomizing Probabilistic Logspace.
In Proceedings of the 21st International Symposium on Theoretical
Aspects of Computer Science, pages 571-583, 2004.
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).
