{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,4]],"date-time":"2026-04-04T05:59:27Z","timestamp":1775282367883,"version":"3.50.1"},"reference-count":37,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2019,4,5]],"date-time":"2019-04-05T00:00:00Z","timestamp":1554422400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100005901","name":"Institute for Advanced Study","doi-asserted-by":"publisher","award":["Friends of the Institute for Advanced Study"],"award-info":[{"award-number":["Friends of the Institute for Advanced Study"]}],"id":[{"id":"10.13039\/100005901","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000893","name":"Simons Foundation","doi-asserted-by":"publisher","award":["Simons Investigator Awards: Impagliazzo, Zuckerman"],"award-info":[{"award-number":["Simons Investigator Awards: Impagliazzo, Zuckerman"]}],"id":[{"id":"10.13039\/100000893","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CCF-0832797, CCF-0916160, CCF-121351, CCF-1526952, CCF-1553605, DMS-0835373"],"award-info":[{"award-number":["CCF-0832797, CCF-0916160, CCF-121351, CCF-1526952, CCF-1553605, DMS-0835373"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["J. ACM"],"published-print":{"date-parts":[[2019,4,30]]},"abstract":"One powerful theme in complexity theory and pseudorandomness in the past few decades has been the use of lower bounds to give pseudorandom generators (PRGs). However, the general results using this hardness vs. randomness paradigm suffer from a quantitative loss in parameters, and hence do not give nontrivial implications for models where we don\u2019t know super-polynomial lower bounds but do know lower bounds of a fixed polynomial. We show that when such lower bounds are proved using random restrictions, we can construct PRGs which are essentially best possible without in turn improving the lower bounds.<\/jats:p>\n \n More specifically, say that a circuit family has shrinkage exponent \u0393 if a random restriction leaving a\n p<\/jats:italic>\n fraction of variables unset shrinks the size of any circuit in the family by a factor of\n p<\/jats:italic>\n \n \u0393 +\n o<\/jats:italic>\n (1)\n <\/jats:sup>\n . Our PRG uses a seed of length\n s<\/jats:italic>\n \n 1\/(\u0393 + 1) +\n o<\/jats:italic>\n (1)\n <\/jats:sup>\n to fool circuits in the family of size\n s<\/jats:italic>\n . By using this generic construction, we get PRGs with polynomially small error for the following classes of circuits of size\n s<\/jats:italic>\n and with the following seed lengths:\n <\/jats:p>\n \n (1) For de Morgan formulas, seed length\n s<\/jats:italic>\n \n 1\/3+\n o<\/jats:italic>\n (1)\n <\/jats:sup>\n ;\n <\/jats:p>\n \n (2) For formulas over an arbitrary basis, seed length\n s<\/jats:italic>\n \n 1\/2+\n o<\/jats:italic>\n (1)\n <\/jats:sup>\n ;\n <\/jats:p>\n \n (3) For read-once de Morgan formulas, seed length\n s<\/jats:italic>\n .234...<\/jats:sup>\n ;\n <\/jats:p>\n \n (4) For branching programs of size\n s<\/jats:italic>\n , seed length\n s<\/jats:italic>\n \n 1\/2+\n o<\/jats:italic>\n (1)\n <\/jats:sup>\n .\n <\/jats:p>\n \n The previous best PRGs known for these classes used seeds of length bigger than\n n<\/jats:italic>\n \/2 to output\n n<\/jats:italic>\n bits, and worked only for size\n s<\/jats:italic>\n =\n O<\/jats:italic>\n (\n n<\/jats:italic>\n ) [8].\n <\/jats:p>","DOI":"10.1145\/3230630","type":"journal-article","created":{"date-parts":[[2019,4,8]],"date-time":"2019-04-08T13:37:23Z","timestamp":1554730643000},"page":"1-16","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":10,"title":["Pseudorandomness from Shrinkage"],"prefix":"10.1145","volume":"66","author":[{"given":"Russell","family":"Impagliazzo","sequence":"first","affiliation":[{"name":"University of California, San Diego"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Raghu","family":"Meka","sequence":"additional","affiliation":[{"name":"University of California, Los Angeles"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"David","family":"Zuckerman","sequence":"additional","affiliation":[{"name":"University of Texas at Austin"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2019,4,5]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1985.19"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(86)90019-2"},{"key":"e_1_2_1_3_1","unstructured":"N. Alon and J. H. Spencer. 2011. The Probabilistic Method. Wiley. N. Alon and J. H. Spencer. 2011. The Probabilistic Method. Wiley."},{"key":"e_1_2_1_4_1","first-page":"63","article-title":"On a method for obtaining more than quadratic effective lower bounds for the complexity of π-schemes","volume":"42","author":"Andreev A. E.","year":"1987","unstructured":"A. E. Andreev . 1987 . On a method for obtaining more than quadratic effective lower bounds for the complexity of π-schemes . Moscow Univ. Math. Bull. 42 , 1 (1987), 63 -- 66 . A. E. Andreev. 1987. On a method for obtaining more than quadratic effective lower bounds for the complexity of π-schemes. Moscow Univ. Math. Bull. 42, 1 (1987), 63--66.","journal-title":"Moscow Univ. Math. Bull."},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.5555\/2033252.2033286"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01275486"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1137\/0213053"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2011.57"},{"key":"e_1_2_1_9_1","first-page":"171","article-title":"Improved pseudorandomness for unordered branching programs through local monotonicity","volume":"24","author":"Chattopadhyay Eshan","year":"2017","unstructured":"Eshan Chattopadhyay , Pooya Hatami , Omer Reingold , and Avishay Tal . 2017 . Improved pseudorandomness for unordered branching programs through local monotonicity . Electronic Colloquium on Computational Complexity (ECCC) 24 (2017), 171 . Eshan Chattopadhyay, Pooya Hatami, Omer Reingold, and Avishay Tal. 2017. Improved pseudorandomness for unordered branching programs through local monotonicity. Electronic Colloquium on Computational Complexity (ECCC) 24 (2017), 171.","journal-title":"Electronic Colloquium on Computational Complexity (ECCC)"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/1538902.1538904"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-85363-3_37"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.5555\/276234.276238"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(94)00081-S"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(02)00024-7"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.3240040202"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/195058.195190"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00037-004-0182-6"},{"key":"e_1_2_1_18_1","first-page":"21","article-title":"Complexity of the realization of a linear function in the class of π-circuits","volume":"9","author":"Khrapchenko V. M.","year":"1971","unstructured":"V. M. Khrapchenko . 1971 . Complexity of the realization of a linear function in the class of π-circuits . Math. Notes Acad. Sciences USSR 9 (1971), 21 -- 23 . V. M. Khrapchenko. 1971. Complexity of the realization of a linear function in the class of π-circuits. Math. Notes Acad. Sciences USSR 9 (1971), 21--23.","journal-title":"Math. Notes Acad. Sciences USSR"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/2488608.2488630"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2013.69"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01375474"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01305237"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(05)80043-1"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1996.0004"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.3240040203"},{"key":"e_1_2_1_26_1","volume-title":"Proceedings of APPROX-RANDOM. 655--670","author":"Reingold O.","unstructured":"O. Reingold , T. Steinke , and S. P. Vadhan . 2013. Pseudorandomness for regular branching programs via fourier analysis . In Proceedings of APPROX-RANDOM. 655--670 . O. Reingold, T. Steinke, and S. P. Vadhan. 2013. Pseudorandomness for regular branching programs via fourier analysis. In Proceedings of APPROX-RANDOM. 655--670."},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1137\/S089548019223872X"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/1374376.1374461"},{"key":"e_1_2_1_29_1","volume-title":"Proceedings of APPROX-RANDOM. 885--899","author":"Steinke Thomas","year":"2014","unstructured":"Thomas Steinke , Salil P. Vadhan , and Andrew Wan . 2014 . Pseudorandomness and Fourier growth bounds for width-3 branching programs . In Proceedings of APPROX-RANDOM. 885--899 . Thomas Steinke, Salil P. Vadhan, and Andrew Wan. 2014. Pseudorandomness and Fourier growth bounds for width-3 branching programs. In Proceedings of APPROX-RANDOM. 885--899."},{"key":"e_1_2_1_30_1","first-page":"110","article-title":"Realizations of linear functions by formulas using +, *, −","volume":"2","author":"Subbotovskaya B. A.","year":"1961","unstructured":"B. A. Subbotovskaya . 1961 . Realizations of linear functions by formulas using +, *, − . Sov. Math. Dokl. 2 (1961), 110 -- 112 . B. A. Subbotovskaya. 1961. Realizations of linear functions by formulas using +, *, −. Sov. Math. Dokl. 2 (1961), 110--112.","journal-title":"Sov. Math. Dokl."},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2014.65"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1109\/CCC.2013.32"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(84)90016-6"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.5555\/2033252.2033312"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/1806689.1806723"},{"key":"e_1_2_1_36_1","volume-title":"Proceedings of the 23rd Annual IEEE Symposium on Foundations of Computer Science. 80--91","author":"Chi-Chih Yao Andrew","year":"1982","unstructured":"Andrew Chi-Chih Yao . 1982 . Theory and applications of trapdoor functions (extended abstract) . In Proceedings of the 23rd Annual IEEE Symposium on Foundations of Computer Science. 80--91 . Andrew Chi-Chih Yao. 1982. Theory and applications of trapdoor functions (extended abstract). In Proceedings of the 23rd Annual IEEE Symposium on Foundations of Computer Science. 80--91."},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.5555\/280032.280035"}],"container-title":["Journal of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3230630","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3230630","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3230630","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T01:39:47Z","timestamp":1750210787000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3230630"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,4,5]]},"references-count":37,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2019,4,30]]}},"alternative-id":["10.1145\/3230630"],"URL":"https:\/\/doi.org\/10.1145\/3230630","relation":{},"ISSN":["0004-5411","1557-735X"],"issn-type":[{"value":"0004-5411","type":"print"},{"value":"1557-735X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2019,4,5]]},"assertion":[{"value":"2017-12-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2018-11-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2019-04-05","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}