{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,23]],"date-time":"2026-08-23T14:42:50Z","timestamp":1787496170241,"version":"build-2736575974"},"publisher-location":"New York, NY, USA","reference-count":54,"publisher":"ACM","license":[{"start":{"date-parts":[[2020,6,22]],"date-time":"2020-06-22T00:00:00Z","timestamp":1592784000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100014718","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CCF-1741615"],"award-info":[{"award-number":["CCF-1741615"]}],"id":[{"id":"10.13039\/100014718","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2020,6,22]]},"DOI":"10.1145\/3357713.3384279","type":"proceedings-article","created":{"date-parts":[[2020,6,6]],"date-time":"2020-06-06T21:45:25Z","timestamp":1591479925000},"page":"1327-1334","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":16,"title":["Strong average-case lower bounds from non-trivial derandomization"],"prefix":"10.1145","author":[{"given":"Lijie","family":"Chen","sequence":"first","affiliation":[{"name":"Massachusetts Institute of Technology, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Hanlin","family":"Ren","sequence":"additional","affiliation":[{"name":"Tsinghua University, China"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2020,6,22]]},"reference":[{"key":"e_1_3_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/1490270.1490272"},{"key":"e_1_3_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1016\/0168-0072(83)90038-6"},{"key":"e_1_3_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2019.00067"},{"key":"e_1_3_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-17367-7"},{"key":"e_1_3_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539705446950"},{"key":"e_1_3_2_1_6_1","volume-title":"Computational Complexity-A Modern Approach","author":"Arora Sanjeev","unstructured":"Sanjeev Arora and Boaz Barak . 2009. Computational Complexity-A Modern Approach . Cambridge University Press . http:\/\/www.cambridge.org\/catalogue\/ catalogue.asp?isbn= 9780521424264 Sanjeev Arora and Boaz Barak. 2009. Computational Complexity-A Modern Approach. Cambridge University Press. http:\/\/www.cambridge.org\/catalogue\/ catalogue.asp?isbn= 9780521424264"},{"key":"e_1_3_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/278298.278306"},{"key":"e_1_3_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/273865.273901"},{"key":"e_1_3_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(87)90036-6"},{"key":"e_1_3_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ITCS.2019.8"},{"key":"e_1_3_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1137\/0204037"},{"key":"e_1_3_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(89)90037-8"},{"key":"e_1_3_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-43948-7_14"},{"key":"e_1_3_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ITCS.2019.13"},{"key":"e_1_3_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-03810-6_25"},{"key":"e_1_3_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ITCS.2019.22"},{"key":"e_1_3_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2019.00079"},{"key":"e_1_3_2_1_18_1","unstructured":"Lijie Chen and Hanlin Ren. 2020. Strong Average-Case Circuit Lower Bounds from Non-trivial Derandomization. Electronic Colloquium on Computational Complexity (ECCC) 27 ( 2020 ) 10. https:\/\/eccc.weizmann. ac.il\/report\/2020\/010  Lijie Chen and Hanlin Ren. 2020. Strong Average-Case Circuit Lower Bounds from Non-trivial Derandomization. Electronic Colloquium on Computational Complexity (ECCC) 27 ( 2020 ) 10. https:\/\/eccc.weizmann. ac.il\/report\/2020\/010"},{"key":"e_1_3_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.CCC.2019.19"},{"key":"e_1_3_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-77404-6_24"},{"key":"e_1_3_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.4086\/toc.2013.v009a026"},{"key":"e_1_3_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01744431"},{"key":"e_1_3_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01200426"},{"key":"e_1_3_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/73007.73010"},{"key":"e_1_3_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/1250790.1250855"},{"key":"e_1_3_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2018.00094"},{"key":"e_1_3_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(93)90001-D"},{"key":"e_1_3_2_1_28_1","unstructured":"Johan H\u00e5stad. 1989. Almost Optimal Lower Bounds for Small Depth Circuits. Advances in Computing Research 5 ( 1989 ) 143-170.  Johan H\u00e5stad. 1989. Almost Optimal Lower Bounds for Small Depth Circuits. Advances in Computing Research 5 ( 1989 ) 143-170."},{"key":"e_1_3_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1137\/080734030"},{"key":"e_1_3_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-45465-9_22"},{"key":"e_1_3_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/62212.62215"},{"key":"e_1_3_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/146585.146605"},{"key":"e_1_3_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1137\/100811623"},{"key":"e_1_3_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/3188745.3188910"},{"key":"e_1_3_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(05)80043-1"},{"key":"e_1_3_2_1_36_1","doi-asserted-by":"crossref","unstructured":"Alexander A Razborov. 1987. Lower bounds on the size of bounded depth circuits over a complete basis with logical addition. Mathematical Notes of the Academy of Sciences of the USSR 41 4 ( 1987 ) 333-338.  Alexander A Razborov. 1987. Lower bounds on the size of bounded depth circuits over a complete basis with logical addition. Mathematical Notes of the Academy of Sciences of the USSR 41 4 ( 1987 ) 333-338.","DOI":"10.1007\/BF01137685"},{"key":"e_1_3_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1997.1494"},{"key":"e_1_3_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/322047.322061"},{"key":"e_1_3_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1137\/080735096"},{"key":"e_1_3_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1145\/146585.146609"},{"key":"e_1_3_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1145\/28395.28404"},{"key":"e_1_3_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1993.366874"},{"key":"e_1_3_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1561\/0400000010"},{"key":"e_1_3_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00037-009-0267-3"},{"key":"e_1_3_2_1_45_1","unstructured":"Emanuele Viola. 2020. New lower bounds for probabilistic degree and AC0 with parity gates. Electronic Colloquium on Computational Complexity (ECCC) 27 ( 2020 ) 15. https:\/\/eccc.weizmann. ac.il\/report\/2020\/015  Emanuele Viola. 2020. New lower bounds for probabilistic degree and AC0 with parity gates. Electronic Colloquium on Computational Complexity (ECCC) 27 ( 2020 ) 15. https:\/\/eccc.weizmann. ac.il\/report\/2020\/015"},{"key":"e_1_3_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.STACS.2020.59"},{"key":"e_1_3_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1137\/10080703X"},{"key":"e_1_3_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1145\/2591796.2591858"},{"key":"e_1_3_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1145\/2559903"},{"key":"e_1_3_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1137\/130938219"},{"key":"e_1_3_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.CCC.2018.6"},{"key":"e_1_3_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1982.45"},{"key":"e_1_3_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1985.49"},{"key":"e_1_3_2_1_54_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(83)90015-4"}],"event":{"name":"STOC '20: 52nd Annual ACM SIGACT Symposium on Theory of Computing","location":"Chicago IL USA","acronym":"STOC '20","sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory"]},"container-title":["Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3357713.3384279","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3357713.3384279","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T18:41:12Z","timestamp":1750185672000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3357713.3384279"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,6,22]]},"references-count":54,"alternative-id":["10.1145\/3357713.3384279","10.1145\/3357713"],"URL":"https:\/\/doi.org\/10.1145\/3357713.3384279","relation":{},"subject":[],"published":{"date-parts":[[2020,6,22]]},"assertion":[{"value":"2020-06-22","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}