Abstract
This is a survey of space-bounded probabilistic computation, summarizing the present state of knowledge about the relationships between the various complexity classes associated with such computation. The survey especially emphasizes recent progress in the construction of pseudorandom generators that fool probabilistic space-bounded computations, and the application of such generators to obtain deterministic simulations.
| Original language | English (US) |
|---|---|
| Pages (from-to) | 128-149 |
| Number of pages | 22 |
| Journal | Proceedings of the Annual IEEE Conference on Computational Complexity |
| State | Published - 1996 |
| Event | Proceedings of the 1996 11th Annual IEEE Conference on Computational Complexity - Philadelphia, PA, USA Duration: May 24 1996 → May 27 1996 |
All Science Journal Classification (ASJC) codes
- Software
- Theoretical Computer Science
- Computational Mathematics