Typically-Correct Derandomization for Small Time and Space
share
Suppose a language L can be decided by a bounded-error randomized algorithm that runs in space S and time n ·poly(S). We give a randomized algorithm for L that still runs in space O(S) and time n ·poly(S) that uses only O(S) random bits; our algorithm has a low failure probability on all but a negligible fraction of inputs of each length. An immediate corollary is a deterministic algorithm for L that runs in space O(S) and succeeds on all but a negligible fraction of inputs of each length. Next, suppose a language L can be decided by a nondeterministic algorithm that runs in space S and time n ·poly(S). We give an unambiguous algorithm for L that runs in space O(S √( S)) and time 2^O(S) that succeeds on all but a negligible fraction of inputs of each length. Finally, we prove that BPL⊆L/(n + O(^2 n)) and NL⊆UL/(n + O(^2 n)), improving results by Fortnow and Klivans (STACS '06) and Reinhardt and Allender (SICOMP '00), respectively. If the original randomized/nondeterministic algorithm runs in quasilinear time, we show that fewer than n bits of advice suffice (for disambiguation, this involves increasing the space complexity to O( n √( n))).
READ FULL TEXT