On recycling the randomness of states in space bounded computation

Ran Raz, Omer Reingold

Research output: Contribution to journalConference articlepeer-review

59 Scopus citations

Abstract

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 languageEnglish (US)
Pages (from-to)159-168
Number of pages10
JournalConference Proceedings of the Annual ACM Symposium on Theory of Computing
DOIs
StatePublished - 1999
Externally publishedYes
EventProceedings of the 1999 31st Annual ACM Symposium on Theory of Computing - FCRC '99 - Atlanta, GA, USA
Duration: May 1 1999May 4 1999

All Science Journal Classification (ASJC) codes

  • Software

Fingerprint Dive into the research topics of 'On recycling the randomness of states in space bounded computation'. Together they form a unique fingerprint.

Cite this