{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,10]],"date-time":"2026-06-10T07:53:55Z","timestamp":1781078035285,"version":"3.54.1"},"reference-count":96,"publisher":"Association for Computing Machinery (ACM)","issue":"6","license":[{"start":{"date-parts":[[2022,11,17]],"date-time":"2022-11-17T00:00:00Z","timestamp":1668643200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"NSF","award":["CCF-1705028"],"award-info":[{"award-number":["CCF-1705028"]}]},{"name":"NSF","award":["CCF-1705028 and CCF-1648712"],"award-info":[{"award-number":["CCF-1705028 and CCF-1648712"]}]},{"name":"NSF","award":["CCF-1705028"],"award-info":[{"award-number":["CCF-1705028"]}]},{"name":"NSF","award":["CCF-1705028 and CCF-2008076"],"award-info":[{"award-number":["CCF-1705028 and CCF-2008076"]}]},{"name":"Simons Investigator Award","award":["409864"],"award-info":[{"award-number":["409864"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["J. ACM"],"published-print":{"date-parts":[[2022,12,31]]},"abstract":"<jats:p>\n            Existing proofs that deduce BPP = P from circuit lower bounds convert randomized algorithms into deterministic algorithms with a large polynomial slowdown. We convert randomized algorithms into deterministic ones with\n            <jats:italic>little slowdown<\/jats:italic>\n            . Specifically, assuming exponential lower bounds against randomized NP \u2229 coNP circuits, formally known as randomized SVN circuits, we convert any randomized algorithm over inputs of length\n            <jats:italic>n<\/jats:italic>\n            running in time\n            <jats:italic>t<\/jats:italic>\n            \u2265\n            <jats:italic>n<\/jats:italic>\n            into a deterministic one running in time\n            <jats:italic>t<\/jats:italic>\n            <jats:sup>2+\u03b1<\/jats:sup>\n            for an arbitrarily small constant \u03b1 &gt; 0. Such a slowdown is nearly optimal for\n            <jats:italic>t<\/jats:italic>\n            close to\n            <jats:italic>n<\/jats:italic>\n            , since under standard complexity-theoretic assumptions, there are problems with an inherent quadratic derandomization slowdown. We also convert any randomized algorithm that\n            <jats:italic>errs rarely<\/jats:italic>\n            into a deterministic algorithm having a similar running time (with pre-processing). The latter derandomization result holds under weaker assumptions, of exponential lower bounds against deterministic SVN circuits.\n          <\/jats:p>\n          <jats:p>\n            Our results follow from a new, nearly optimal, explicit pseudorandom generator fooling circuits of size\n            <jats:italic>s<\/jats:italic>\n            with seed length (1+\u03b1)log\n            <jats:italic>s<\/jats:italic>\n            , under the assumption that there exists a function\n            <jats:italic>f<\/jats:italic>\n            \u2208 E that requires randomized SVN circuits of size at least 2\n            <jats:sup>(1-\u03b1\u2032)<\/jats:sup>\n            <jats:italic>n<\/jats:italic>\n            , where \u03b1 =\n            <jats:italic>O<\/jats:italic>\n            (\u03b1)\u2032. The construction uses, among other ideas, a new connection between pseudoentropy generators and locally list recoverable codes.\n          <\/jats:p>","DOI":"10.1145\/3555307","type":"journal-article","created":{"date-parts":[[2022,8,10]],"date-time":"2022-08-10T12:20:09Z","timestamp":1660134009000},"page":"1-55","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":10,"title":["Nearly Optimal Pseudorandomness from Hardness"],"prefix":"10.1145","volume":"69","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-1862-8341","authenticated-orcid":false,"given":"Dean","family":"Doron","sequence":"first","affiliation":[{"name":"Ben Gurion University of the Negev, Beer-Sheva, Israel"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-4151-568X","authenticated-orcid":false,"given":"Dana","family":"Moshkovitz","sequence":"additional","affiliation":[{"name":"University of Texas at Austin, Austin, Texas, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-4422-6365","authenticated-orcid":false,"given":"Justin","family":"Oh","sequence":"additional","affiliation":[{"name":"University of Texas at Austin, Austin, Texas, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-4749-3223","authenticated-orcid":false,"given":"David","family":"Zuckerman","sequence":"additional","affiliation":[{"name":"University of Texas at Austin, Austin, Texas, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2022,11,17]]},"reference":[{"key":"e_1_3_3_2_2","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1978.37"},{"key":"e_1_3_3_3_2","doi-asserted-by":"publisher","DOI":"10.1109\/18.119713"},{"key":"e_1_3_3_4_2","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1995.492581"},{"key":"e_1_3_3_5_2","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.3240030308"},{"key":"e_1_3_3_6_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00037-016-0128-9"},{"key":"e_1_3_3_7_2","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539796297577"},{"key":"e_1_3_3_8_2","doi-asserted-by":"publisher","DOI":"10.5555\/2982445.2982454"},{"key":"e_1_3_3_9_2","doi-asserted-by":"publisher","DOI":"10.1145\/3018057"},{"key":"e_1_3_3_10_2","doi-asserted-by":"publisher","DOI":"10.1007\/BFb0058034"},{"key":"e_1_3_3_11_2","doi-asserted-by":"publisher","DOI":"10.1137\/050641958"},{"key":"e_1_3_3_12_2","doi-asserted-by":"publisher","DOI":"10.4007\/annals.2012.176.3.3"},{"key":"e_1_3_3_13_2","doi-asserted-by":"crossref","first-page":"200","DOI":"10.1007\/978-3-540-45198-3_18","volume-title":"Approximation, Randomization, and Combinatorial Optimization\u2014Algorithms and Techniques","author":"Barak Boaz","year":"2003","unstructured":"Boaz Barak, Ronen Shaltiel, and Avi Wigderson. 2003. Computational analogues of entropy. In Approximation, Randomization, and Combinatorial Optimization\u2014Algorithms and Techniques. Springer, 200\u2013215."},{"key":"e_1_3_3_14_2","doi-asserted-by":"publisher","DOI":"10.1145\/3313276.3316333"},{"key":"e_1_3_3_15_2","doi-asserted-by":"publisher","DOI":"10.1145\/3406325.3451059"},{"key":"e_1_3_3_16_2","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS52979.2021.00021"},{"key":"e_1_3_3_17_2","volume-title":"Proceedings of the Electronic Colloquium on Computational Complexity (ECCC)","author":"Chen Lijie","year":"2022","unstructured":"Lijie Chen and Roei Tell. 2022. When Arthur has neither random coins nor time to spare: Superfast derandomization of proof systems. In Proceedings of the Electronic Colloquium on Computational Complexity (ECCC)."},{"key":"e_1_3_3_18_2","doi-asserted-by":"publisher","DOI":"10.5555\/2033036.2033048"},{"key":"e_1_3_3_19_2","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2016.27"},{"key":"e_1_3_3_20_2","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975482.129"},{"key":"e_1_3_3_21_2","doi-asserted-by":"publisher","DOI":"10.1137\/060651380"},{"key":"e_1_3_3_22_2","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2013.84"},{"key":"e_1_3_3_23_2","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2008.56"},{"key":"e_1_3_3_24_2","doi-asserted-by":"publisher","DOI":"10.4086\/toc.2013.v009a026"},{"key":"e_1_3_3_25_2","doi-asserted-by":"publisher","DOI":"10.1215\/S0012-7094-03-11812-8"},{"key":"e_1_3_3_26_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00145-013-9174-5"},{"key":"e_1_3_3_27_2","first-page":"466","article-title":"Computational entropy and information leakage.","volume":"2012","author":"Fuller Benjamin","year":"2012","unstructured":"Benjamin Fuller and Leonid Reyzin. 2012. Computational entropy and information leakage. IACR Cryptology ePrint Archive 2012 (2012), 466.","journal-title":"IACR Cryptology ePrint Archive"},{"key":"e_1_3_3_28_2","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(81)90040-4"},{"key":"e_1_3_3_29_2","doi-asserted-by":"publisher","DOI":"10.1007\/s10958-013-1350-5"},{"key":"e_1_3_3_30_2","doi-asserted-by":"publisher","DOI":"10.1145\/3039872"},{"key":"e_1_3_3_31_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-39206-1_39"},{"key":"e_1_3_3_32_2","volume-title":"Proceedings of the Electronic Colloquium on Computational Complexity (ECCC)","author":"Goldreich Oded","year":"1997","unstructured":"Oded Goldreich. 1997. A sample of samplers: A computational perspective on sampling. In Proceedings of the Electronic Colloquium on Computational Complexity (ECCC)."},{"key":"e_1_3_3_33_2","doi-asserted-by":"publisher","DOI":"10.1145\/285055.285060"},{"key":"e_1_3_3_34_2","doi-asserted-by":"publisher","DOI":"10.1145\/2591796.2591808"},{"key":"e_1_3_3_35_2","doi-asserted-by":"publisher","DOI":"10.5555\/280032.280034"},{"key":"e_1_3_3_36_2","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-45726-7_17"},{"key":"e_1_3_3_37_2","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2018.2809788"},{"key":"e_1_3_3_38_2","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2018.00094"},{"key":"e_1_3_3_39_2","doi-asserted-by":"publisher","DOI":"10.1145\/509907.510023"},{"key":"e_1_3_3_40_2","doi-asserted-by":"publisher","DOI":"10.1145\/780542.780562"},{"key":"e_1_3_3_41_2","doi-asserted-by":"publisher","DOI":"10.1145\/780542.780562"},{"key":"e_1_3_3_42_2","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2007.911222"},{"key":"e_1_3_3_43_2","article-title":"Essential coding theory","author":"Guruswami Venkatesan","year":"2019","unstructured":"Venkatesan Guruswami, Atri Rudra, and Madhu Sudan. 2019. Essential coding theory. Retrieved from https:\/\/cse.buffalo.edu\/faculty\/atri\/courses\/coding-theory\/book.","journal-title":"https:\/\/cse.buffalo.edu\/faculty\/atri\/courses\/coding-theory\/book"},{"key":"e_1_3_3_44_2","doi-asserted-by":"publisher","DOI":"10.1145\/1538902.1538904"},{"key":"e_1_3_3_45_2","doi-asserted-by":"crossref","first-page":"455","DOI":"10.1007\/978-3-540-85363-3_36","volume-title":"Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques","author":"Gutfreund Dan","year":"2008","unstructured":"Dan Gutfreund and Guy N. Rothblum. 2008. The complexity of local list decoding. In Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques. Springer, 455\u2013468."},{"key":"e_1_3_3_46_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00037-003-0178-7"},{"key":"e_1_3_3_47_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-48000-7_9"},{"key":"e_1_3_3_48_2","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539793244708"},{"key":"e_1_3_3_49_2","doi-asserted-by":"publisher","DOI":"10.1137\/17M116149X"},{"key":"e_1_3_3_50_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.ic.2018.02.004"},{"key":"e_1_3_3_51_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-72540-4_10"},{"key":"e_1_3_3_52_2","doi-asserted-by":"publisher","DOI":"10.1145\/258533.258590"},{"key":"e_1_3_3_53_2","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973075.91"},{"key":"e_1_3_3_54_2","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.1972.1054893"},{"key":"e_1_3_3_55_2","doi-asserted-by":"publisher","DOI":"10.1137\/08073408X"},{"key":"e_1_3_3_56_2","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539700389652"},{"key":"e_1_3_3_57_2","doi-asserted-by":"publisher","DOI":"10.1145\/3051093"},{"key":"e_1_3_3_58_2","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2018.00029"},{"key":"e_1_3_3_59_2","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2016.16"},{"key":"e_1_3_3_60_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00037-005-0197-7"},{"key":"e_1_3_3_61_2","first-page":"42:1\u201342:22","volume-title":"Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX\/RANDOM\u201919)","author":"Murtagh Jack","year":"2019","unstructured":"Jack Murtagh, Omer Reingold, Aaron Sidford, and Salil Vadhan. 2019. Deterministic approximation of random walks in small space. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX\/RANDOM\u201919). Schloss Dagstuhl\u2013Leibniz-Zentrum fuer Informatik, 42:1\u201342:22."},{"key":"e_1_3_3_62_2","doi-asserted-by":"publisher","DOI":"10.1137\/0222053"},{"key":"e_1_3_3_63_2","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(05)80043-1"},{"key":"e_1_3_3_64_2","doi-asserted-by":"publisher","DOI":"10.1145\/322123.322138"},{"key":"e_1_3_3_65_2","doi-asserted-by":"publisher","DOI":"10.1137\/S0895480197329508"},{"key":"e_1_3_3_66_2","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.2002.1824"},{"key":"e_1_3_3_67_2","author":"Reingold Omer","year":"2003","unstructured":"Omer Reingold. 2003. Personal Communication.","journal-title":"Personal Communication"},{"key":"e_1_3_3_68_2","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539703431032"},{"key":"e_1_3_3_69_2","doi-asserted-by":"publisher","DOI":"10.2307\/3062153"},{"key":"e_1_3_3_70_2","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975031.42"},{"key":"e_1_3_3_71_2","doi-asserted-by":"publisher","DOI":"10.1145\/1059513.1059516"},{"key":"e_1_3_3_72_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00037-007-0218-9"},{"key":"e_1_3_3_73_2","doi-asserted-by":"publisher","DOI":"10.1145\/1250790.1250854"},{"key":"e_1_3_3_74_2","volume-title":"Proceedings of the 13th Innovations in Theoretical Computer Science Conference (ITCS\u201922)","author":"Shaltiel Ronen","year":"2022","unstructured":"Ronen Shaltiel and Emanuele Viola. 2022. On hardness assumptions needed for \u201cExtreme High-End\u201d PRGs and fast derandomization. In Proceedings of the 13th Innovations in Theoretical Computer Science Conference (ITCS\u201922). Schloss Dagstuhl-Leibniz-Zentrum f\u00fcr Informatik."},{"key":"e_1_3_3_75_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-17470-9_7"},{"key":"e_1_3_3_76_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-47672-7_85"},{"key":"e_1_3_3_77_2","doi-asserted-by":"publisher","DOI":"10.1006\/jcom.1997.0439"},{"key":"e_1_3_3_78_2","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.2000.1730"},{"key":"e_1_3_3_79_2","doi-asserted-by":"publisher","DOI":"10.1145\/3055399.3055408"},{"key":"e_1_3_3_80_2","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2004.838377"},{"key":"e_1_3_3_81_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2005.05.010"},{"key":"e_1_3_3_82_2","doi-asserted-by":"publisher","DOI":"10.1145\/3188745.3188822"},{"key":"e_1_3_3_83_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00037-019-00179-2"},{"key":"e_1_3_3_84_2","doi-asserted-by":"publisher","DOI":"10.1145\/502090.502099"},{"key":"e_1_3_3_85_2","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.2000.892063"},{"key":"e_1_3_3_86_2","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(03)00046-1"},{"key":"e_1_3_3_87_2","doi-asserted-by":"publisher","DOI":"10.1561\/0400000010"},{"key":"e_1_3_3_88_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00200-012-0179-3"},{"key":"e_1_3_3_89_2","doi-asserted-by":"publisher","DOI":"10.1109\/CCC.2003.1214410"},{"key":"e_1_3_3_90_2","doi-asserted-by":"publisher","DOI":"10.5555\/2512973"},{"key":"e_1_3_3_91_2","doi-asserted-by":"publisher","DOI":"10.5555\/1009378.1009540"},{"key":"e_1_3_3_92_2","doi-asserted-by":"publisher","DOI":"10.1145\/2422436.2422451"},{"key":"e_1_3_3_93_2","first-page":"2:1\u20132:17","volume-title":"Proceedings of the 31st Annual Conference on Computational Complexity (CCC\u201916)","author":"Williams Ryan","year":"2016","unstructured":"Ryan Williams. 2016. Strong ETH breaks with Merlin and Arthur: Short non-interactive proofs of batch evaluation. In Proceedings of the 31st Annual Conference on Computational Complexity (CCC\u201916). 2:1\u20132:17."},{"key":"e_1_3_3_94_2","doi-asserted-by":"publisher","DOI":"10.5555\/1382436.1382790"},{"key":"e_1_3_3_95_2","doi-asserted-by":"publisher","DOI":"10.1561\/0400000030"},{"key":"e_1_3_3_96_2","doi-asserted-by":"publisher","DOI":"10.5555\/280032.280035"},{"key":"e_1_3_3_97_2","doi-asserted-by":"publisher","DOI":"10.4086\/toc.2007.v003a006"}],"container-title":["Journal of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3555307","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3555307","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3555307","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T17:49:02Z","timestamp":1750182542000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3555307"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,11,17]]},"references-count":96,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2022,12,31]]}},"alternative-id":["10.1145\/3555307"],"URL":"https:\/\/doi.org\/10.1145\/3555307","relation":{},"ISSN":["0004-5411","1557-735X"],"issn-type":[{"value":"0004-5411","type":"print"},{"value":"1557-735X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,11,17]]},"assertion":[{"value":"2021-05-28","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2022-08-02","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2022-11-17","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}