Title :
Hardness vs. randomness
Author :
Nisan, N. ; Wigderson, Avi
Author_Institution :
Div. of Comput. Sci., California Univ., Berkeley, CA
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
Keywords :
computational complexity; random number generation; arbitrary function; complexity class C; hardness; lower bounds; pseudorandom bit generator; randomness; Random sequences;
Conference_Titel :
Foundations of Computer Science, 1988., 29th Annual Symposium on
Conference_Location :
White Plains, NY
Print_ISBN :
0-8186-0877-3
DOI :
10.1109/SFCS.1988.21916
