Randomness is linear in space
| Author(s) : | David Zuckerman Noam Nisan, |
| Publisher : | N/A |
| Publication Date : | 1996 |
| ISSN : | N/A |
| Abstract : | We show that any randomized algorithm that runs in space S and time T and uses poly(S) random bits can be simulated using only O(S) random bits in space S and time T + poly(S). A deterministic simulation in space S follows. 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. 1, |