Typically-Correct Derandomization for Small Time and Space

Suppose a language $L$ can be decided by a bounded-error randomized algorithm that runs in space $S$ and time $n \cdot \text{poly}(S)$. We give a randomized algorithm for $L$ that still runs in space $O(S)$ and time $n \cdot \text{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. As an immediate corollary, there 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. We also give several other complexity-theoretic applications of our technique.

A "randomized" algorithm tosses coins to make decisions, whereas a "deterministic" algorithm doesn't use any randomness. Most theoretical computer scientists believe that if a problem can be solved by a randomized algorithm, then it can also be solved by a deterministic algorithm that uses about the same amount of time and memory. But nobody knows how to prove it. In this paper, we prove that if a problem can be solved by a fast randomized algorithm, then it can also be solved by a deterministic algorithm that uses about the same amount of memory, with the caveat that the deterministic algorithm might give the wrong answer on a tiny fraction of inputs.