2017/11/01 by William M. Hoza, Hoza, William M.
Computer Science · #Computational Complexity (cs.CC) #FOS: Computer and information sciences #cs.CC
paper · pdf · doi:10.48550/arxiv.1711.00565
39 pages, 9 figures. Improved presentation, simplified content
arxiv created 2019/05/15 · arxiv updated 2019/05/17
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. We also give several other complexity-theoretic applications of our technique.