{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T17:13:30Z","timestamp":1760202810441,"version":"3.41.0"},"publisher-location":"New York, NY, USA","reference-count":21,"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"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2020,6,22]]},"DOI":"10.1145\/3357713.3384242","type":"proceedings-article","created":{"date-parts":[[2020,6,7]],"date-time":"2020-06-07T01:45:25Z","timestamp":1591494325000},"page":"234-246","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":3,"title":["XOR lemmas for resilient functions against polynomials"],"prefix":"10.1145","author":[{"given":"Eshan","family":"Chattopadhyay","sequence":"first","affiliation":[{"name":"Cornell University, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Pooya","family":"Hatami","sequence":"additional","affiliation":[{"name":"Ohio State University, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Kaave","family":"Hosseini","sequence":"additional","affiliation":[{"name":"Carnegie Mellon University, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Shachar","family":"Lovett","sequence":"additional","affiliation":[{"name":"University of California at San Diego, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"David","family":"Zuckerman","sequence":"additional","affiliation":[{"name":"University of Texas at Austin, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2020,6,22]]},"reference":[{"doi-asserted-by":"crossref","unstructured":"natorica 13 2 ( 1993 ) 129-145. natorica 13 2 ( 1993 ) 129-145.","key":"e_1_3_2_1_1_1","DOI":"10.1007\/BF01303199"},{"doi-asserted-by":"crossref","unstructured":"System Sci. 45 2 ( 1992 ) 204-232. System Sci. 45 2 ( 1992 ) 204-232.","key":"e_1_3_2_1_2_1","DOI":"10.1016\/0022-0000(92)90047-M"},{"key":"e_1_3_2_1_3_1","volume-title":"Noam Nisan, and M\u00e1ri\u00f3 Szegedy.","author":"Ajtai Mikl\u00f3s","year":"1992","unstructured":"Mikl\u00f3s Ajtai and Nathan Linial . 1993. The influence of large coalitions. Combi L\u00e1szl\u00f3 Babai , Noam Nisan, and M\u00e1ri\u00f3 Szegedy. 1992 . Mikl\u00f3s Ajtai and Nathan Linial. 1993. The influence of large coalitions. Combi L\u00e1szl\u00f3 Babai, Noam Nisan, and M\u00e1ri\u00f3 Szegedy. 1992."},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_4_1","DOI":"10.1109\/SFCS.1985.15"},{"doi-asserted-by":"crossref","unstructured":"Jean Bourgain. 2005. Estimation of certain exponential sums arising in complexity theory. Comptes Rendus Mathematique 340 9 ( 2005 ) 627-631. Jean Bourgain. 2005. Estimation of certain exponential sums arising in complexity theory. Comptes Rendus Mathematique 340 9 ( 2005 ) 627-631.","key":"e_1_3_2_1_5_1","DOI":"10.1016\/j.crma.2005.03.008"},{"unstructured":"Eshan Chattopadhyay Pooya Hatami Kaave Hosseini and Shachar Lovett. 2018. Eshan Chattopadhyay Pooya Hatami Kaave Hosseini and Shachar Lovett. 2018.","key":"e_1_3_2_1_6_1"},{"key":"e_1_3_2_1_7_1","volume-title":"33rd Computational Complexity Conference (CCC 2018 ). Schloss Dagstuhl-Leibniz-Zentrum fuer Infor Eshan Chattopadhyay, Pooya Hatami, Shachar Lovett, and Avishay Tal.","author":"Pseudorandom","year":"2019","unstructured":"Pseudorandom generators from polarizing random walks . In 33rd Computational Complexity Conference (CCC 2018 ). Schloss Dagstuhl-Leibniz-Zentrum fuer Infor Eshan Chattopadhyay, Pooya Hatami, Shachar Lovett, and Avishay Tal. 2019 . Pseudorandom generators from polarizing random walks. In 33rd Computational Complexity Conference (CCC 2018 ). Schloss Dagstuhl-Leibniz-Zentrum fuer Infor Eshan Chattopadhyay, Pooya Hatami, Shachar Lovett, and Avishay Tal. 2019."},{"key":"e_1_3_2_1_8_1","volume-title":"Proceedings of the twenty-first annual ACM symposium on Theory of Alexander Golovnev, Alexander S. Kulikov, and Ryan Williams. 2019","author":"Chattopadhyay Eshan","year":"2019","unstructured":"Eshan Chattopadhyay and David Zuckerman . 2019 . Explicit two-source extractors and resilient functions. Annals of Mathematics 189, 3 ( 2019 ), 653-705. https: Oded Goldreich and Leonid A Levin. 1989. A hard-core predicate for all one-way functions . In Proceedings of the twenty-first annual ACM symposium on Theory of Alexander Golovnev, Alexander S. Kulikov, and Ryan Williams. 2019 . Circuit Depth Reductions. CoRR abs\/ 1811.04828 ( 2019 ). arXiv: 1811.04828 http:\/\/arxiv. Eshan Chattopadhyay and David Zuckerman. 2019. Explicit two-source extractors and resilient functions. Annals of Mathematics 189, 3 ( 2019 ), 653-705. https: Oded Goldreich and Leonid A Levin. 1989. A hard-core predicate for all one-way functions. In Proceedings of the twenty-first annual ACM symposium on Theory of Alexander Golovnev, Alexander S. Kulikov, and Ryan Williams. 2019. Circuit Depth Reductions. CoRR abs\/ 1811.04828 ( 2019 ). arXiv: 1811.04828 http:\/\/arxiv."},{"key":"e_1_3_2_1_9_1","first-page":"73","volume-title":"Proceedings of the Edinburgh Mathematical Society 51","author":"Green Ben","year":"2008","unstructured":"Ben Green and Terence Tao . 2008 . An inverse theorem for the Gowers U3(G) norm . Proceedings of the Edinburgh Mathematical Society 51 , 1 ( 2008 ), 73 - 153 . Ben Green and Terence Tao. 2008. An inverse theorem for the Gowers U3(G) norm. Proceedings of the Edinburgh Mathematical Society 51, 1 ( 2008 ), 73-153."},{"key":"e_1_3_2_1_10_1","first-page":"679","volume-title":"29th Annual Symposium on Foundations of Computer Science. IEEE, [ 13 ] Shachar Lovett, Partha Mukhopadhyay, and Amir Shpilka. 2013","author":"Green Frederic","year":"2005","unstructured":"Frederic Green , Amitabha Roy , and Howard Straubing . 2005 . Bounds on an exponential sum arising in Boolean circuit complexity. Comptes Rendus Mathematique Jef Kahn, Gil Kalai, and Nathan Linial. 1988. The influence of variables on Boolean functions . In 29th Annual Symposium on Foundations of Computer Science. IEEE, [ 13 ] Shachar Lovett, Partha Mukhopadhyay, and Amir Shpilka. 2013 . Pseudorandom generators for CC0[p] and the Fourier spectrum of low-degree polynomials over ifnite fields. Computational Complexity 22, 4 ( 2013 ), 679 - 725 . Frederic Green, Amitabha Roy, and Howard Straubing. 2005. Bounds on an exponential sum arising in Boolean circuit complexity. Comptes Rendus Mathematique Jef Kahn, Gil Kalai, and Nathan Linial. 1988. The influence of variables on Boolean functions. In 29th Annual Symposium on Foundations of Computer Science. IEEE, [ 13 ] Shachar Lovett, Partha Mukhopadhyay, and Amir Shpilka. 2013. Pseudorandom generators for CC0[p] and the Fourier spectrum of low-degree polynomials over ifnite fields. Computational Complexity 22, 4 ( 2013 ), 679-725."},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_11_1","DOI":"10.5555\/3039686.3039759"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_12_1","DOI":"10.1016\/S0022-0000(05)80043-1"},{"volume-title":"Analysis of Boolean functions","author":"O'Donnell Ryan","unstructured":"Ryan O'Donnell . 2014. Analysis of Boolean functions . Cambridge University Press . Ryan O'Donnell. 2014. Analysis of Boolean functions. Cambridge University Press.","key":"e_1_3_2_1_13_1"},{"doi-asserted-by":"crossref","unstructured":"Alexander A Razborov. 1987. Lower bounds on the dimension of schemes of bounded depth in a complete basis containing the logical addition function. Mat. Zametki 41 4 ( 1987 ) 598-607. Alexander A Razborov. 1987. Lower bounds on the dimension of schemes of bounded depth in a complete basis containing the logical addition function. Mat. Zametki 41 4 ( 1987 ) 598-607.","key":"e_1_3_2_1_14_1","DOI":"10.1007\/BF01137685"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_15_1","DOI":"10.1145\/28395.28404"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_16_1","DOI":"10.1109\/SFCS.1993.366874"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_18_1","DOI":"10.1109\/SFCS.1984.715948"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_19_1","DOI":"10.1145\/1515698.1515709"},{"unstructured":"Emanuele Viola. 2019. Matching Smolensky's correlation bound with majority. ( 2019 ). Emanuele Viola. 2019. Matching Smolensky's correlation bound with majority. ( 2019 ).","key":"e_1_3_2_1_20_1"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_21_1","DOI":"10.1109\/CCC.2007.15"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_22_1","DOI":"10.1109\/SFCS.1982.45"}],"event":{"sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory"],"acronym":"STOC '20","name":"STOC '20: 52nd Annual ACM SIGACT Symposium on Theory of Computing","location":"Chicago IL USA"},"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.3384242","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3357713.3384242","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T22:41:12Z","timestamp":1750200072000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3357713.3384242"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,6,22]]},"references-count":21,"alternative-id":["10.1145\/3357713.3384242","10.1145\/3357713"],"URL":"https:\/\/doi.org\/10.1145\/3357713.3384242","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"}}]}}