Using Hard Problems to Create Pseudorandom Generators
应用数学Randomization is an important tool in the design of algorithms, and theability of randomization to provide enhanced power is a major research topic incomplexity theory. Noam Nisan continues the investigation into the power ofrandomization and the relationships between randomized and deterministic complexityclasses by pursuing the idea of emulating randomness, or pseudorandomgeneration.Pseudorandom generators reduce the number of random bits required byrandomized algorithms, enable the construction of certain cryptographic proto