{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,10]],"date-time":"2026-06-10T08:00:14Z","timestamp":1781078414854,"version":"3.54.1"},"publisher-location":"New York, NY, USA","reference-count":30,"publisher":"ACM","license":[{"start":{"date-parts":[[2021,6,15]],"date-time":"2021-06-15T00:00:00Z","timestamp":1623715200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by-nd\/4.0\/"}],"funder":[{"name":"Google Faculty Research Award"},{"DOI":"10.13039\/100000001","name":"NSF (National Science Foundation)","doi-asserted-by":"publisher","award":["CCF-1741615"],"award-info":[{"award-number":["CCF-1741615"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"name":"IBM Fellowship"},{"name":"European Research Council (ERC)","award":["819702"],"award-info":[{"award-number":["819702"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2021,6,15]]},"DOI":"10.1145\/3406325.3451059","type":"proceedings-article","created":{"date-parts":[[2021,6,16]],"date-time":"2021-06-16T01:26:13Z","timestamp":1623806773000},"page":"283-291","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":16,"title":["Simple and fast derandomization from very hard functions: eliminating randomness at almost no cost"],"prefix":"10.1145","author":[{"given":"Lijie","family":"Chen","sequence":"first","affiliation":[{"name":"Massachusetts Institute of Technology, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Roei","family":"Tell","sequence":"additional","affiliation":[{"name":"Massachusetts Institute of Technology, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2021,6,15]]},"reference":[{"key":"e_1_3_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/273865.273933"},{"key":"e_1_3_2_1_2_1","volume-title":"Proc. 31st Annual IEEE Conference on Computational Complexity (CCC). Pages Art. No. 9, 35","author":"Artemenko Sergei","year":"2016","unstructured":"Sergei Artemenko, Russell Impagliazzo, Valentine Kabanets, and Ronen Shaltiel. 2016. Pseudorandomness when the odds are against you. In Proc. 31st Annual IEEE Conference on Computational Complexity (CCC). Pages Art. No. 9, 35."},{"key":"e_1_3_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-45198-3_18"},{"key":"e_1_3_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1137\/110839229"},{"key":"e_1_3_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1137\/0213053"},{"key":"e_1_3_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/3357713.3384283"},{"key":"e_1_3_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/3313276.3316333"},{"key":"e_1_3_2_1_8_1","first-page":"2020","article-title":"Simple and fast derandomization from very hard functions: Eliminating randomness at almost no cost","volume":"27","author":"Chen Lijie","year":"2020","unstructured":"Lijie Chen and Roei Tell. 2020. Simple and fast derandomization from very hard functions: Eliminating randomness at almost no cost. Electronic Colloquium on Computational Complexity: ECCC, 27, 2020. Pages 148.","journal-title":"Electronic Colloquium on Computational Complexity: ECCC"},{"key":"e_1_3_2_1_9_1","first-page":"1","article-title":"Average-case lower bounds and satisfiability algorithms for small threshold circuits. In Proc. 31st Annual IEEE Conference on Computational Complexity (CCC)","volume":"1","author":"Chen Ruiwen","year":"2016","unstructured":"Ruiwen Chen, Rahul Santhanam, and Srikanth Srinivasan. 2016. Average-case lower bounds and satisfiability algorithms for small threshold circuits. In Proc. 31st Annual IEEE Conference on Computational Complexity (CCC). Pages 1:1\u20131:35.","journal-title":"Pages"},{"key":"e_1_3_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/3148227"},{"key":"e_1_3_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS46700.2020.00102"},{"key":"e_1_3_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.4086\/toc.2013.v009a026"},{"key":"e_1_3_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/2591796.2591808"},{"key":"e_1_3_2_1_14_1","first-page":"4","article-title":"A Pseudorandom Generator from any One-way Function","volume":"28","author":"Johan","year":"1999","unstructured":"Johan H\\r astad, Russell Impagliazzo, Leonid A. Levin, and Michael Luby. 1999. A Pseudorandom Generator from any One-way Function. SIAM Journal of Computing, 28, 4, 1999. Pages 1364\u20131396.","journal-title":"SIAM Journal of Computing"},{"key":"e_1_3_2_1_15_1","volume-title":"Proc. 29th Annual ACM Symposium on Theory of Computing (STOC). Pages 220\u2013229","author":"Impagliazzo Russell","year":"1999","unstructured":"Russell Impagliazzo and Avi Wigderson. 1999. \\rm P=\\rm BPP if \\rm E requires exponential circuits: derandomizing the XOR lemma. In Proc. 29th Annual ACM Symposium on Theory of Computing (STOC). Pages 220\u2013229."},{"key":"e_1_3_2_1_16_1","volume-title":"Proc. 22th International Workshop on Randomization and Approximation Techniques in Computer Science (RANDOM). LIPIcs. Leibniz Int. Proc. Inform.. 116","author":"Kabanets Valentine","year":"2018","unstructured":"Valentine Kabanets and Zhenjian Lu. 2018. Satisfiability and derandomization for small polynomial threshold circuits. In Proc. 22th International Workshop on Randomization and Approximation Techniques in Computer Science (RANDOM). LIPIcs. Leibniz Int. Proc. Inform.. 116, Pages Art. No. 46, 19."},{"key":"e_1_3_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611974782.143"},{"key":"e_1_3_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00037-005-0197-7"},{"key":"e_1_3_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(05)80043-1"},{"key":"e_1_3_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/1066100.1066101"},{"key":"e_1_3_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.2002.1824"},{"key":"e_1_3_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/1059513.1059516"},{"key":"e_1_3_2_1_23_1","doi-asserted-by":"crossref","unstructured":"Michael Sipser. 1988. Expanders randomness or time versus space. 36 Pages 379\u2013383.","DOI":"10.1016\/0022-0000(88)90035-9"},{"key":"e_1_3_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.2000.1730"},{"key":"e_1_3_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2005.05.010"},{"key":"e_1_3_2_1_26_1","first-page":"1","article-title":"Improved Bounds for Quantified Derandomization of Constant-Depth Circuits and Polynomials. In Proc. 32nd Annual IEEE Conference on Computational Complexity (CCC)","volume":"18","author":"Tell Roei","year":"2017","unstructured":"Roei Tell. 2017. Improved Bounds for Quantified Derandomization of Constant-Depth Circuits and Polynomials. In Proc. 32nd Annual IEEE Conference on Computational Complexity (CCC). Pages 18:1 \u2013 18:49.","journal-title":"Pages"},{"key":"e_1_3_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/3188745.3188822"},{"key":"e_1_3_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(03)00046-1"},{"key":"e_1_3_2_1_29_1","volume-title":"Proc. 31st Annual IEEE Conference on Computational Complexity (CCC). 50","author":"Williams Richard Ryan","year":"2016","unstructured":"Richard Ryan Williams. 2016. Strong ETH breaks with Merlin and Arthur: short non-interactive proofs of batch evaluation. In Proc. 31st Annual IEEE Conference on Computational Complexity (CCC). 50, Pages Art. No. 2, 17."},{"key":"e_1_3_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1982.45"}],"event":{"name":"STOC '21: 53rd Annual ACM SIGACT Symposium on Theory of Computing","location":"Virtual Italy","acronym":"STOC '21","sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory"]},"container-title":["Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3406325.3451059","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3406325.3451059","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3406325.3451059","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T22:01:45Z","timestamp":1750197705000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3406325.3451059"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,6,15]]},"references-count":30,"alternative-id":["10.1145\/3406325.3451059","10.1145\/3406325"],"URL":"https:\/\/doi.org\/10.1145\/3406325.3451059","relation":{},"subject":[],"published":{"date-parts":[[2021,6,15]]},"assertion":[{"value":"2021-06-15","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}