{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,23]],"date-time":"2026-08-23T17:50:42Z","timestamp":1787507442719,"version":"build-2736575974"},"publisher-location":"New York, NY, USA","reference-count":50,"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\/4.0\/"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2021,6,15]]},"DOI":"10.1145\/3406325.3451132","type":"proceedings-article","created":{"date-parts":[[2021,6,15]],"date-time":"2021-06-15T21:26:13Z","timestamp":1623792373000},"page":"761-771","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":8,"title":["Inverse-exponential correlation bounds and extremely rigid matrices from a new derandomized XOR lemma"],"prefix":"10.1145","author":[{"given":"Lijie","family":"Chen","sequence":"first","affiliation":[{"name":"Massachusetts Institute of Technology, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Xin","family":"Lyu","sequence":"additional","affiliation":[{"name":"Tsinghua University, China"}],"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.1109\/FOCS.2019.00067"},{"key":"e_1_3_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(92)90047-M"},{"key":"e_1_3_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973068.129"},{"key":"e_1_3_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01263423"},{"key":"e_1_3_2_1_5_1","volume-title":"Proc. 61st FOCS. IEEE Comp. Soc.. https:\/\/eccc.weizmann.ac.il\/report\/2020\/075\/","author":"Bhangale Amey","year":"2020","unstructured":"Amey Bhangale, Prahladh Harsha, Orr Paradise, and Avishay Tal. 2020. Rigid Matrices From Rectangular PCPs. In Proc. 61st FOCS. IEEE Comp. Soc.. https:\/\/eccc.weizmann.ac.il\/report\/2020\/075\/"},{"key":"e_1_3_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.crma.2005.03.008"},{"key":"e_1_3_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1137\/18M1197734"},{"key":"e_1_3_2_1_8_1","first-page":"2020","article-title":"Fractional Pseudorandom Generators from Any Fourier Level","volume":"27","author":"Chattopadhyay Eshan","year":"2020","unstructured":"Eshan Chattopadhyay, Jason Gaitonde, Chin Ho Lee, Shachar Lovett, and Abhishek Shetty. 2020. Fractional Pseudorandom Generators from Any Fourier Level. Electron. Colloquium Comput. Complex., 27, 2020. Pages 121. https:\/\/eccc.weizmann.ac.il\/report\/2020\/121","journal-title":"Electron. Colloquium Comput. Complex."},{"key":"e_1_3_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/3357713.3384242"},{"key":"e_1_3_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ITCS.2019.22"},{"key":"e_1_3_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.CCC.2020.25"},{"key":"e_1_3_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS46700.2020.00009"},{"key":"e_1_3_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/3357713.3384279"},{"key":"e_1_3_2_1_14_1","volume-title":"Proc. 34th Conf. Computational Complexity (CCC'19)","author":"Chen Lijie","year":"2019","unstructured":"Lijie Chen and R. Ryan Williams. 2019. Stronger Connections Between Circuit Analysis and Circuit Lower Bounds, via PCPs of Proximity. In Proc. 34th Conf. Computational Complexity (CCC'19). Schloss Dagstuhl\u2013Leibniz-Zentrum fuer Informatik. Pages 19:1\u201319:43. http:\/\/drops.dagstuhl.de\/opus\/volltexte\/2019\/10841"},{"key":"e_1_3_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2018.00093"},{"key":"e_1_3_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-22670-0_23"},{"key":"e_1_3_2_1_17_1","first-page":"2018","article-title":"Circuit Depth Reductions","volume":"25","author":"Golovnev Alexander","year":"2018","unstructured":"Alexander Golovnev, Alexander S. Kulikov, and R. Ryan Williams. 2018. Circuit Depth Reductions. Electron. Colloquium Comput. Complex., 25, 2018. Pages 192. https:\/\/eccc.weizmann.ac.il\/report\/2018\/192","journal-title":"Electron. Colloquium Comput. Complex."},{"key":"e_1_3_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.crma.2005.07.011"},{"key":"e_1_3_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1137\/17M1129088"},{"key":"e_1_3_2_1_20_1","first-page":"1989","article-title":"Almost Optimal Lower Bounds for Small Depth","volume":"5","author":"Johan","year":"1989","unstructured":"Johan H\\r astad. 1989. Almost Optimal Lower Bounds for Small Depth Circuits. Adv. Comput. Res., 5, 1989. Pages 143\u2013170.","journal-title":"Circuits. Adv. Comput. Res."},{"key":"e_1_3_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539705447281"},{"key":"e_1_3_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/1060590.1060689"},{"key":"e_1_3_2_1_23_1","first-page":"2020","article-title":"Average-case rigidity lower bounds","volume":"26","author":"Huang Xuangui","year":"2020","unstructured":"Xuangui Huang and Emanuele Viola. 2020. Average-case rigidity lower bounds. Electron. Colloquium Comput. Complex., 26, 2020. Pages 175. https:\/\/eccc.weizmann.ac.il\/report\/2019\/175","journal-title":"Electron. Colloquium Comput. Complex."},{"key":"e_1_3_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1995.492584"},{"key":"e_1_3_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/258533.258590"},{"key":"e_1_3_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.4086\/toc.2018.v014a012"},{"key":"e_1_3_2_1_27_1","first-page":"2017","article-title":"More on bounded independence plus noise: Pseudorandom generators for read-once polynomials","volume":"24","author":"Lee Chin Ho","year":"2017","unstructured":"Chin Ho Lee and Emanuele Viola. 2017. More on bounded independence plus noise: Pseudorandom generators for read-once polynomials. Electron. Colloquium Comput. Complex., 24, 2017. Pages 167. https:\/\/eccc.weizmann.ac.il\/report\/2017\/167","journal-title":"Electron. Colloquium Comput. Complex."},{"key":"e_1_3_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02579323"},{"key":"e_1_3_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/3313276.3316339"},{"key":"e_1_3_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1561\/0400000011"},{"key":"e_1_3_2_1_31_1","unstructured":"Zhenjian Lu. 2020. Personal Communication."},{"key":"e_1_3_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01305237"},{"key":"e_1_3_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(05)80043-1"},{"key":"e_1_3_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.CCC.2019.23"},{"key":"e_1_3_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.MFCS.2018.78"},{"key":"e_1_3_2_1_36_1","first-page":"4","article-title":"Lower bounds on the size of bounded depth circuits over a complete basis with logical addition","volume":"41","author":"Razborov Alexander A.","year":"1987","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. Pages 333\u2013338.","journal-title":"Mathematical Notes of the Academy of Sciences of the USSR"},{"key":"e_1_3_2_1_37_1","unstructured":"Alexander A. Razborov. 1989. On rigid matrices (in Russian). http:\/\/people.cs.uchicago.edu\/~razborov\/files\/rigid.pdf"},{"key":"e_1_3_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2008.38"},{"key":"e_1_3_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1145\/28395.28404"},{"key":"e_1_3_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1993.366874"},{"key":"e_1_3_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1109\/CCC.2009.41"},{"key":"e_1_3_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-08353-7_135"},{"key":"e_1_3_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1145\/1515698.1515709"},{"key":"e_1_3_2_1_44_1","first-page":"2020","article-title":"Matching Smolensky's correlation bound with majority","volume":"20","author":"Viola Emanuele","year":"2020","unstructured":"Emanuele Viola. 2020. Matching Smolensky's correlation bound with majority. Electron. Colloquium Comput. Complex., 20, 2020. Pages 193. https:\/\/eccc.weizmann.ac.il\/report\/2020\/193\/","journal-title":"Electron. Colloquium Comput. Complex."},{"key":"e_1_3_2_1_45_1","first-page":"2020","article-title":"New lower bounds for probabilistic degree and AC0 with parity gates","volume":"27","author":"Viola Emanuele","year":"2020","unstructured":"Emanuele Viola. 2020. New lower bounds for probabilistic degree and AC0 with parity gates. Electron. Colloquium Comput. Complex., 27, 2020. Pages 15. https:\/\/eccc.weizmann.ac.il\/report\/2020\/015","journal-title":"Electron. Colloquium Comput. Complex."},{"key":"e_1_3_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.4086\/toc.2008.v004a007"},{"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\/2559903"},{"key":"e_1_3_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1982.45"},{"key":"e_1_3_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1109\/FSCS.1990.89583"}],"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.3451132","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3406325.3451132","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T17:24:53Z","timestamp":1750181093000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3406325.3451132"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,6,15]]},"references-count":50,"alternative-id":["10.1145\/3406325.3451132","10.1145\/3406325"],"URL":"https:\/\/doi.org\/10.1145\/3406325.3451132","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"}}]}}