Title :
Randomization and derandomization in space-bounded computation
Author_Institution :
Dept. of Math., Rutgers Univ., New Brunswick, NJ, USA
Abstract :
This is a survey of spacebounded 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
Keywords :
bibliographies; computational complexity; randomised algorithms; complexity classes; derandomization; deterministic simulations; probabilistic space-bounded computations; pseudorandom generators; randomization; space-bounded computation; Complexity theory; Computational modeling; Computer applications; Contracts; Cryptography; Marine vehicles; Mathematics; Polynomials; Random number generation; Testing;
Conference_Titel :
Computational Complexity, 1996. Proceedings., Eleventh Annual IEEE Conference on
Conference_Location :
Philadelphia, PA
Print_ISBN :
0-8186-7386-9
DOI :
10.1109/CCC.1996.507676
