Hardness vs. Randomness (Extended Abstract)

A simple construction for a pseudorandom bit generator is presented. It stretches a short string of truly random bits into a long string that looks random to any algorithm from a complexity class C (e. g. P, NC, PSPACE, etc.), using an arbitrary function that is hard for C. This generator reveals an equivalence between the problems of proving lower bounds and the problem of generating good pseudorandom sequences. Combining this construction with other arguments, a number of consequences are obtained. >

Authors

• Noam Nisan
• Avi Wigderson

Keywords

• Random sequences
• Cardinality
• Hardness
• Random Generation
• Complex Class
• Pseudo-random
• Hypothesis H1
• Efficient Simulation
• Proof Of The Lemma
• Exponential Time
• Boolean Function
• Input Fractions
• Constant Depth
• Lemma States
• Random Bits
• Turing Machine
• Set Of Languages
• Small Circuit
• Random Oracle