{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T17:09:18Z","timestamp":1760202558706},"reference-count":14,"publisher":"Wiley","issue":"2","license":[{"start":{"date-parts":[[2007,3,9]],"date-time":"2007-03-09T00:00:00Z","timestamp":1173398400000},"content-version":"vor","delay-in-days":5546,"URL":"http:\/\/onlinelibrary.wiley.com\/termsAndConditions#vor"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Random Struct Algorithms"],"published-print":{"date-parts":[[1992,1]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>The existence of <jats:italic>sparse pseudorandom<\/jats:italic> distributions is proved. These are probability distributions concentrated in a very small set of strings, yet it is infeasible for any polynomial\u2010time 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\u2010time algorithms cannot even approximate all the pseudorandom distributions. Moreover, we show the existence of <jats:italic>evasive<\/jats:italic> pseudorandom distributions which are not only sparse, but also have the property that no polynomial\u2010time algorithm may find an element in their support, except for a negligible probability. All these results are proved independently of any intractability assumption.<\/jats:p>","DOI":"10.1002\/rsa.3240030206","type":"journal-article","created":{"date-parts":[[2007,5,31]],"date-time":"2007-05-31T08:51:38Z","timestamp":1180601498000},"page":"163-174","source":"Crossref","is-referenced-by-count":15,"title":["Sparse pseudorandom distributions"],"prefix":"10.1002","volume":"3","author":[{"given":"Oded","family":"Goldreich","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Hugo","family":"Krawczyk","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"311","published-online":{"date-parts":[[2007,3,9]]},"reference":[{"key":"e_1_2_1_2_2","doi-asserted-by":"publisher","DOI":"10.1137\/0213053"},{"key":"e_1_2_1_3_2","doi-asserted-by":"publisher","DOI":"10.1214\/aoms\/1177729330"},{"key":"e_1_2_1_4_2","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(90)90010-U"},{"issue":"4","key":"e_1_2_1_5_2","first-page":"792","volume":"33","author":"Goldreich O.","year":"1986","journal-title":"How to construct random functions"},{"key":"e_1_2_1_6_2","first-page":"268","volume-title":"17th ICALP Proceedings, Lecture Notes in Computer Science","author":"Goldreich O.","year":"1990"},{"key":"e_1_2_1_7_2","doi-asserted-by":"crossref","unstructured":"O.Goldreich H.Krawczyk andM.Luby On the existence of pseudorandom generators Proc. 29th IEEE Symp. on Foundation of Computer Science 1988 pp.12\u201324.","DOI":"10.1109\/SFCS.1988.21917"},{"key":"e_1_2_1_8_2","doi-asserted-by":"crossref","unstructured":"J.Hastad Pseudo\u2010random generators under uniform assumptions Proc. 22nd STOC 1990.","DOI":"10.1145\/100216.100270"},{"key":"e_1_2_1_9_2","doi-asserted-by":"publisher","DOI":"10.1080\/01621459.1963.10500830"},{"key":"e_1_2_1_10_2","doi-asserted-by":"crossref","unstructured":"R.Impagliazzo L. A.Levin andM. G.Luby Pseudo\u2010random generation from one\u2010way functions Proc. 21st STOC 1989 pp.12\u201324.","DOI":"10.1145\/73007.73009"},{"key":"e_1_2_1_11_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF02579323"},{"key":"e_1_2_1_12_2","doi-asserted-by":"crossref","unstructured":"L. A.Levin Homogeneous measures and polynomial time invariants Proc. 29th IEEE Symp. on Foundation of Computer Science 1988 pp.36\u201341.","DOI":"10.1109\/SFCS.1988.21919"},{"key":"e_1_2_1_13_2","doi-asserted-by":"publisher","DOI":"10.1137\/0217022"},{"key":"e_1_2_1_14_2","doi-asserted-by":"crossref","unstructured":"N.NisanandA.Wigderson Hardness vs. randomness Proc. 29th IEEE Symp. on Foundation of Computer Science 1988 pp.2\u201311.","DOI":"10.1109\/SFCS.1988.21916"},{"key":"e_1_2_1_15_2","doi-asserted-by":"crossref","unstructured":"A. C.Yao Theory and applications of trapdoor functions Proc. 23rd IEEE Symp. on Foundation of Computer Science 1982 pp.80\u201391.","DOI":"10.1109\/SFCS.1982.45"}],"container-title":["Random Structures &amp; Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.wiley.com\/onlinelibrary\/tdm\/v1\/articles\/10.1002%2Frsa.3240030206","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/pdf\/10.1002\/rsa.3240030206","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,10,15]],"date-time":"2023-10-15T13:50:35Z","timestamp":1697377835000},"score":1,"resource":{"primary":{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/10.1002\/rsa.3240030206"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1992,1]]},"references-count":14,"journal-issue":{"issue":"2","published-print":{"date-parts":[[1992,1]]}},"alternative-id":["10.1002\/rsa.3240030206"],"URL":"https:\/\/doi.org\/10.1002\/rsa.3240030206","archive":["Portico"],"relation":{},"ISSN":["1042-9832","1098-2418"],"issn-type":[{"value":"1042-9832","type":"print"},{"value":"1098-2418","type":"electronic"}],"subject":[],"published":{"date-parts":[[1992,1]]}}}