Randomization and derandomization in space-bounded computation

Research output: Contribution to journalConference articlepeer-review

42 Scopus citations

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 languageEnglish (US)
Pages (from-to)128-149
Number of pages22
JournalProceedings of the Annual IEEE Conference on Computational Complexity
StatePublished - 1996
EventProceedings of the 1996 11th Annual IEEE Conference on Computational Complexity - Philadelphia, PA, USA
Duration: May 24 1996May 27 1996

All Science Journal Classification (ASJC) codes

  • Software
  • Theoretical Computer Science
  • Computational Mathematics

Fingerprint

Dive into the research topics of 'Randomization and derandomization in space-bounded computation'. Together they form a unique fingerprint.

Cite this