Randomness is Linear in Space

摘要

We show that any randomized algorithm that runs in spaceSand timeTand uses poly(S) random bits can be simulated using onlyO(S) random bits in spaceSand timeT+poly(S). A deterministic simulation in spaceSfollows. Of independent interest is our main technical tool: a procedure which extracts randomness from a defective random source using a small additional number of truly random bits.