Problems / theoretical-computer-science
theoretical-computer-science / Space-bounded derandomization
Derandomization of logarithmic space: is L = RL = BPL?
Claims L=RL=BPL: every language decided with bounded one-sided or two-sided error by a randomized machine with polynomial worst-case running time and O(logn) space is decided by a deterministic O(logn)-space machine. Quantitatively, acceptance probabilities can be approximated to within 2−q in space O(log(n+2)+q) and time (n+2)O(1)2O(q). The method builds a hierarchy of copies of the configuration graph with a shared finite random environment and evaluates a family of O(logn)-bit estimators, more than three quarters of them accurate, by exhaustive enumeration. It does not give a pseudorandom generator with logarithmic seed, and it does not address randomized logspace without a polynomial time bound.