On recycling the randomness of states in space bounded computation
Ran Raz, Omer Reingold · 1999
Let M be a logarithmic space Turing machine (or a polynomial width branching program) that uses up to k 2 p log n (read once) random bits. For a fixed input, let P i (S) be the probability (over the random string) that at time i the machine M is in state S, and assume that some weak estimation of the probabilities P i (S) is known or given or can be easily computed. We construct a logarithmic space pseudo-random generator that uses only logarithmic number of truly random bits and outputs a sequence of k bits that looks random to M . This means that a very weak estimation of the state probabilities of M is sufficient for a full derandomization of M and for constructing pseudo-random sequences for M . We have several applications of the main theorem, as stated within. To prove our theorem, we introduce the idea of recycling the state S of the machine M at time i as part of the random string for the same machine at later time. That is, we use the entropy of the random variable S in o...