Venkat Chakaravarthy(University of Wisconsin, Madison):
Time-Space Tradeoff in Derandomizing Probabilistic Logarithmic Space
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 in simultaneous polynomial time and
O(log^2 n) space. Subsequently Saks and Zhou improved the space bound
and showed that the deterministic simulation can be carried out in
space O(log^1.5 n). But their simulation runs in time
n^{O(log^{0.5} n)}. 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 can be simulated
deterministically, in time n^{O(log^{0.5-a} n)} and space
O(log^{1.5+a}n)). That is, we prove that,
BPL is contained in DTISP[n^{O(log^{0.5-a}n)}, O(log^{1.5+a}n)].
The talk will not assume any prior familiarity with this topic. We
will start with the Nisan generator for space bounded computations, and dis-
cuss first Nisan's algorithm and then the algorithm by Saks and Zhou.
We then discuss the difficulties involved in this interpolation between
the two results, before coming to the new algorithm for the
time-space tradeoff theorem. This talk will be a two part talk that will be
continued at next week's meeting.
Joint work with Jin-Yi Cai and Dieter van Melkebeek.