{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,18]],"date-time":"2025-11-18T09:52:24Z","timestamp":1763459544249,"version":"3.45.0"},"publisher-location":"New York, NY, USA","reference-count":43,"publisher":"ACM","license":[{"start":{"date-parts":[[2017,1,14]],"date-time":"2017-01-14T00:00:00Z","timestamp":1484352000000},"content-version":"vor","delay-in-days":366,"URL":"http:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100003977","name":"Israel Science Foundation","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100003977","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","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":[[2016,1,14]]},"DOI":"10.1145\/2840728.2840734","type":"proceedings-article","created":{"date-parts":[[2016,1,5]],"date-time":"2016-01-05T09:26:11Z","timestamp":1451985971000},"page":"47-58","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":3,"title":["The Complexity of DNF of Parities"],"prefix":"10.1145","author":[{"given":"Gil","family":"Cohen","sequence":"first","affiliation":[{"name":"Caltech, Pasadena, CA, USA"}]},{"given":"Igor","family":"Shinkar","sequence":"additional","affiliation":[{"name":"NYU, New York, NY, USA"}]}],"member":"320","published-online":{"date-parts":[[2016,1,14]]},"reference":[{"key":"e_1_3_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/2554797.2554821"},{"key":"e_1_3_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1109\/CCC.2013.28"},{"key":"e_1_3_2_1_3_1","first-page":"59","volume-title":"27th International Symposium on Theoretical Aspects of Computer Science-STACS 2010","author":"Arvind V.","year":"2010","unstructured":"V. Arvind and S. Srinivasan. The remote point problem, small bias space, and expanding generator sets. In 27th International Symposium on Theoretical Aspects of Computer Science-STACS 2010, pages 59--70, 2010."},{"key":"e_1_3_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-03685-9_28"},{"key":"e_1_3_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1987.30"},{"key":"e_1_3_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/1060590.1060592"},{"key":"e_1_3_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(83)90029-4"},{"key":"e_1_3_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00039-007-0593-z"},{"key":"e_1_3_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1137\/110826254"},{"key":"e_1_3_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/1993636.1993661"},{"key":"e_1_3_2_1_11_1","volume-title":"Elements of information theory","author":"Cover T. M.","year":"2012","unstructured":"T. M. Cover and A. J. Thomas. Elements of information theory. John Wiley & Sons, 2012."},{"key":"e_1_3_2_1_12_1","volume-title":"Two structural results for low degree polynomials and applications. arXiv preprint arXiv:1404.0654","author":"Cohen G.","year":"2014","unstructured":"G. Cohen and A. Tal. Two structural results for low degree polynomials and applications. arXiv preprint arXiv:1404.0654, 2014."},{"key":"e_1_3_2_1_13_1","volume-title":"Teubner","author":"Dickson L. E.","year":"1901","unstructured":"L. E. Dickson. Linear groups with an exposition of the Galois field theory. B.G Teubner's Sammlung von Lehrbuchern auf dem Gebiete der mathematischen Wissenschaften mit Einschluss ihrer Anwendungen. B.G. Teubner, 1901."},{"key":"e_1_3_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.5555\/2034006.2034033"},{"key":"e_1_3_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1016\/0890-5401(89)90001-1"},{"key":"e_1_3_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/195058.195108"},{"key":"e_1_3_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(91)90323-T"},{"key":"e_1_3_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/1806689.1806736"},{"key":"e_1_3_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1997.1533"},{"key":"e_1_3_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1007\/s000370050005"},{"key":"e_1_3_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548306007620"},{"key":"e_1_3_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.5555\/2190632"},{"key":"e_1_3_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2008.17"},{"key":"e_1_3_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1137\/0222080"},{"key":"e_1_3_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1109\/CCC.2011.27"},{"issue":"5","key":"e_1_3_2_1_26_1","first-page":"1041","article-title":"On realization of functions of propositional calculus by formulas of bounded depth over the basis &,vee,neg","volume":"136","author":"Lupanov O.","year":"1961","unstructured":"O. Lupanov. On realization of functions of propositional calculus by formulas of bounded depth over the basis &,vee,neg. Dokl. Akad. Nauk SSSR, 136(5):1041--1042, 1961.","journal-title":"Dokl. Akad. Nauk SSSR"},{"key":"e_1_3_2_1_27_1","volume-title":"On the communication complexity of XOR functions. arXiv preprint arXiv:0909.3392","author":"Montanaro A.","year":"2009","unstructured":"A. Montanaro and T. Osborne. On the communication complexity of XOR functions. arXiv preprint arXiv:0909.3392, 2009."},{"key":"e_1_3_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.5555\/2683783"},{"key":"e_1_3_2_1_29_1","volume-title":"A composition theorem for parity kill number. arXiv preprint arXiv:1312.2143","author":"O'Donnell R.","year":"2013","unstructured":"R. O'Donnell, X. Sun, L. Y. Tan, J. Wright, and Y. Zhao. A composition theorem for parity kill number. arXiv preprint arXiv:1312.2143, 2013."},{"key":"e_1_3_2_1_30_1","first-page":"327","article-title":"Pseudorandom sets and explicit constructions of Ramsey graphs","volume":"13","author":"Pudl\u00e1k P.","year":"2004","unstructured":"P. Pudl\u00e1k and V. R\u00f6dl. Pseudorandom sets and explicit constructions of Ramsey graphs. Quad. Mat, 13:327--346, 2004.","journal-title":"Quad. Mat"},{"key":"e_1_3_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/258533.258556"},{"key":"e_1_3_2_1_32_1","volume-title":"Sociedade Matematica Mexicana","author":"Quine W.","year":"1953","unstructured":"W. Quine. Two theorems about truth functions. Sociedade Matematica Mexicana, 1953."},{"key":"e_1_3_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2011.37"},{"key":"e_1_3_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1109\/CCC.2012.29"},{"key":"e_1_3_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00037-013-0067-7"},{"key":"e_1_3_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/2554797.2554803"},{"key":"e_1_3_2_1_37_1","volume-title":"On a special case of rigidity","author":"Servedio R. A.","year":"2012","unstructured":"R. A. Servedio and E. Viola. On a special case of rigidity. 2012. http:\/\/eccc.hpi-web.de\/report\/2012\/144\/."},{"key":"e_1_3_2_1_38_1","volume-title":"Query complexity, or why is it difficult to separate NPA \u2229 coNPA from PA by random a oracle A Combinatorica, 9(4):385--392","author":"Tardos G.","year":"1989","unstructured":"G. Tardos. Query complexity, or why is it difficult to separate NPA \u2229 coNPA from PA by random a oracle A Combinatorica, 9(4):385--392, 1989."},{"key":"e_1_3_2_1_39_1","volume-title":"Fourier sparsity, spectral norm, and the log-rank conjecture. arXiv preprint arXiv:1304.1245","author":"Tsang H. Y.","year":"2013","unstructured":"H. Y. Tsang, C. H. Wong, N. Xie, and S. Zhang. Fourier sparsity, spectral norm, and the log-rank conjecture. arXiv preprint arXiv:1304.1245, 2013."},{"key":"e_1_3_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1137\/11085983X"},{"key":"e_1_3_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1109\/CCC.2007.15"},{"key":"e_1_3_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00493-011-2604-9"},{"key":"e_1_3_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2010.03.027"}],"event":{"name":"ITCS'16: Innovations in Theoretical Computer Science","sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory"],"location":"Cambridge Massachusetts USA","acronym":"ITCS'16"},"container-title":["Proceedings of the 2016 ACM Conference on Innovations in Theoretical Computer Science"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2840728.2840734","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2840728.2840734","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2840728.2840734","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,11,18]],"date-time":"2025-11-18T09:48:20Z","timestamp":1763459300000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2840728.2840734"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016,1,14]]},"references-count":43,"alternative-id":["10.1145\/2840728.2840734","10.1145\/2840728"],"URL":"https:\/\/doi.org\/10.1145\/2840728.2840734","relation":{},"subject":[],"published":{"date-parts":[[2016,1,14]]},"assertion":[{"value":"2016-01-14","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}