Premium
Sparse pseudorandom distributions
Author(s) -
Goldreich Oded,
Krawczyk Hugo
Publication year - 1992
Publication title -
random structures and algorithms
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.314
H-Index - 69
eISSN - 1098-2418
pISSN - 1042-9832
DOI - 10.1002/rsa.3240030206
Subject(s) - pseudorandom number generator , probabilistic logic , probability distribution , pseudorandomness , mathematics , polynomial , property (philosophy) , algorithm , time complexity , probabilistic analysis of algorithms , set (abstract data type) , discrete mathematics , combinatorics , computer science , statistics , mathematical analysis , philosophy , epistemology , programming language
The existence of sparse pseudorandom distributions is proved. These are probability distributions concentrated in a very small set of strings, yet it is infeasible for any polynomial‐time algorithm to distinguish between truly random coins and coins selected according to these distributions. It is shown that such distributions can be generated by (nonpolynomial) probabilistic algorithms, while probabilistic polynomial‐time algorithms cannot even approximate all the pseudorandom distributions. Moreover, we show the existence of evasive pseudorandom distributions which are not only sparse, but also have the property that no polynomial‐time algorithm may find an element in their support, except for a negligible probability. All these results are proved independently of any intractability assumption.