{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,4]],"date-time":"2026-04-04T05:58:14Z","timestamp":1775282294268,"version":"3.50.1"},"publisher-location":"New York, NY, USA","reference-count":33,"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:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100000001","name":"NSF (National Science Foundation)","doi-asserted-by":"publisher","award":["CCF-1814788"],"award-info":[{"award-number":["CCF-1814788"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2021,6,15]]},"DOI":"10.1145\/3406325.3451054","type":"proceedings-article","created":{"date-parts":[[2021,6,16]],"date-time":"2021-06-16T01:26:13Z","timestamp":1623806773000},"page":"272-282","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":1,"title":["An improved derandomization of the switching lemma"],"prefix":"10.1145","author":[{"given":"Zander","family":"Kelley","sequence":"first","affiliation":[{"name":"University of Illinois at Urbana-Champaign, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2021,6,15]]},"reference":[{"key":"e_1_3_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1985.19"},{"key":"e_1_3_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.3240030308"},{"key":"e_1_3_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/3357713.3384234"},{"key":"e_1_3_2_1_4_1","first-page":"2","article-title":"Pseudorandom generators with optimal seed length for non-boolean poly-size circuits","volume":"9","author":"Artemenko Sergei","year":"2017","unstructured":"Sergei Artemenko and Ronen Shaltiel. 2017. Pseudorandom generators with optimal seed length for non-boolean poly-size circuits. ACM Transactions on Computation Theory (TOCT), 9, 2, 2017. Pages 1\u201326.","journal-title":"ACM Transactions on Computation Theory (TOCT)"},{"key":"e_1_3_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2018.00083"},{"key":"e_1_3_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1137\/070691954"},{"key":"e_1_3_2_1_7_1","first-page":"5","article-title":"Polylogarithmic independence fools AC0 circuits","volume":"57","author":"Braverman Mark","year":"2008","unstructured":"Mark Braverman. 2008. Polylogarithmic independence fools AC0 circuits. Journal of the ACM (JACM), 57, 5, 2008. Pages 1\u201310.","journal-title":"Journal of the ACM (JACM)"},{"key":"e_1_3_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.4086\/toc.2019.v015a010"},{"key":"e_1_3_2_1_9_1","volume-title":"Approximation, randomization, and combinatorial optimization. Algorithms and techniques","author":"De Anindya","unstructured":"Anindya De, Omid Etesami, Luca Trevisan, and Madhur Tulsiani. 2010. Improved pseudorandom generators for depth 2 circuits. In Approximation, randomization, and combinatorial optimization. Algorithms and techniques. Springer. Pages 504\u2013517."},{"key":"e_1_3_2_1_10_1","volume-title":"Near-Optimal Pseudorandom Generators for Constant-Depth Read-Once Formulas. In 34th Computational Complexity Conference (CCC","author":"Doron Dean","year":"2019","unstructured":"Dean Doron, Pooya Hatami, and William M. Hoza. 2019. Near-Optimal Pseudorandom Generators for Constant-Depth Read-Once Formulas. In 34th Computational Complexity Conference (CCC 2019)."},{"key":"e_1_3_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/2591796.2591808"},{"key":"e_1_3_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00037-013-0068-6"},{"key":"e_1_3_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.20786"},{"key":"e_1_3_2_1_14_1","volume-title":"Proceedings of the eighteenth annual ACM symposium on Theory of computing. Pages 6\u201320","author":"Johan","year":"1986","unstructured":"Johan H\\r astad. 1986. Almost optimal lower bounds for small depth circuits. In Proceedings of the eighteenth annual ACM symposium on Theory of computing. Pages 6\u201320."},{"key":"e_1_3_2_1_15_1","first-page":"5","article-title":"On the correlation of parity and small-depth circuits","volume":"43","author":"Johan","year":"2014","unstructured":"Johan H\\r astad. 2014. On the correlation of parity and small-depth circuits. SIAM J. Comput., 43, 5, 2014. Pages 1699\u20131708.","journal-title":"SIAM J. Comput."},{"key":"e_1_3_2_1_16_1","volume-title":"Boolean function complexity: advances and frontiers. 27","author":"Jukna Stasys","unstructured":"Stasys Jukna. 2012. Boolean function complexity: advances and frontiers. 27, Springer Science & Business Media."},{"key":"e_1_3_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/174130.174138"},{"key":"e_1_3_2_1_18_1","unstructured":"Shachar Lovett Raghu Meka and Jiapeng Zhang. 2020. Improved lifting theorems via robust sunflowers. In Electronic Colloquium on Computational Complexity (ECCC). 27 Pages 48."},{"key":"e_1_3_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/3357713.3384241"},{"key":"e_1_3_2_1_20_1","first-page":"2","article-title":"Lifting","volume":"1","author":"Mertz Ian","year":"2020","unstructured":"Ian Mertz and Toniann Pitassi. 2020. Lifting: As Easy As 1,2,3. In Electronic Colloquium on Computational Complexity (ECCC).","journal-title":"As Easy As"},{"key":"e_1_3_2_1_21_1","series-title":"SIAM journal on computing, 22, 4","volume-title":"Small-bias probability spaces: Efficient constructions and applications","author":"Naor Joseph","year":"1993","unstructured":"Joseph Naor and Moni Naor. 1993. Small-bias probability spaces: Efficient constructions and applications. SIAM journal on computing, 22, 4, 1993. Pages 838\u2013856."},{"key":"e_1_3_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01375474"},{"key":"e_1_3_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/1490270.1490273"},{"key":"e_1_3_2_1_24_1","volume-title":"Bounded arithmetic and lower bounds in Boolean complexity","author":"Razborov Alexander A","unstructured":"Alexander A Razborov. 1995. Bounded arithmetic and lower bounds in Boolean complexity. In Feasible Mathematics II. Springer. Pages 344\u2013386."},{"key":"e_1_3_2_1_25_1","volume-title":"Criticality of Regular Formulas. In 34th Computational Complexity Conference (CCC","author":"Rossman Benjamin","year":"2019","unstructured":"Benjamin Rossman. 2019. Criticality of Regular Formulas. In 34th Computational Complexity Conference (CCC 2019)."},{"key":"e_1_3_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1137\/S089548019223872X"},{"key":"e_1_3_2_1_27_1","volume-title":"2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS). Pages 813\u2013823","author":"Rocco","unstructured":"Rocco A. Servedio and Li-Yang Tan. 2017. Deterministic search for CNF satisfying assignments in almost polynomial time. In 2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS). Pages 813\u2013823."},{"key":"e_1_3_2_1_28_1","volume-title":"Servedio and Li-Yang Tan","author":"Rocco","year":"2019","unstructured":"Rocco A. Servedio and Li-Yang Tan. 2019. Improved Pseudorandom Generators from Pseudorandom Multi-Switching Lemmas. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX\/RANDOM 2019)."},{"key":"e_1_3_2_1_29_1","volume-title":"Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX\/RANDOM","author":"Shaltiel Ronen","year":"2016","unstructured":"Ronen Shaltiel and Jad Silbak. 2016. Explicit list-decodable codes with optimal rate for computationally bounded channels. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX\/RANDOM 2016)."},{"key":"e_1_3_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.5555\/3135595.3135610"},{"key":"e_1_3_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00037-019-00179-2"},{"key":"e_1_3_2_1_32_1","volume-title":"Notes on switching lemmas","author":"Thapen Neil","year":"2009","unstructured":"Neil Thapen. 2009. Notes on switching lemmas. 2009."},{"key":"e_1_3_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1109\/CCC.2013.32"}],"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.3451054","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3406325.3451054","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3406325.3451054","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T22:01:44Z","timestamp":1750197704000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3406325.3451054"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,6,15]]},"references-count":33,"alternative-id":["10.1145\/3406325.3451054","10.1145\/3406325"],"URL":"https:\/\/doi.org\/10.1145\/3406325.3451054","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"}}]}}