Let M be a logarithmic space Turing machine (or a polynomial width branching program) that uses up to k≈2√log n (read once) random bits. For a fixed input, let Pi(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 Pi(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 order to save truly random bits later on. Our techniques and results can both be generalized to larger size of space.
|Original language||English (US)|
|Number of pages||10|
|Journal||Conference Proceedings of the Annual ACM Symposium on Theory of Computing|
|State||Published - 1999|
|Event||Proceedings of the 1999 31st Annual ACM Symposium on Theory of Computing - FCRC '99 - Atlanta, GA, USA|
Duration: May 1 1999 → May 4 1999
All Science Journal Classification (ASJC) codes