## 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 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 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) |
---|---|

Pages (from-to) | 159-168 |

Number of pages | 10 |

Journal | Conference Proceedings of the Annual ACM Symposium on Theory of Computing |

DOIs | |

State | Published - 1999 |

Externally published | Yes |

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

- Software