{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T04:47:08Z","timestamp":1750308428368,"version":"3.41.0"},"publisher-location":"New York, NY, USA","reference-count":60,"publisher":"ACM","license":[{"start":{"date-parts":[[2022,6,9]],"date-time":"2022-06-09T00:00:00Z","timestamp":1654732800000},"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":[[2022,6,9]]},"DOI":"10.1145\/3519935.3520000","type":"proceedings-article","created":{"date-parts":[[2022,6,10]],"date-time":"2022-06-10T15:29:32Z","timestamp":1654874972000},"page":"1194-1207","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":1,"title":["The approximate degree of DNF and CNF formulas"],"prefix":"10.1145","author":[{"given":"Alexander A.","family":"Sherstov","sequence":"first","affiliation":[{"name":"University of California at Los Angeles, USA"}]}],"member":"320","published-online":{"date-parts":[[2022,6,10]]},"reference":[{"key":"e_1_3_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.4086\/toc.2005.v001a001"},{"key":"e_1_3_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/1008731.1008735"},{"key":"e_1_3_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1112\/blms\/22.6.583"},{"key":"e_1_3_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.4086\/toc.2005.v001a003"},{"key":"e_1_3_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1137\/080712167"},{"key":"e_1_3_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01215346"},{"key":"e_1_3_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1986.15"},{"key":"e_1_3_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(92)90047-M"},{"key":"e_1_3_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2003.11.006"},{"key":"e_1_3_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/502090.502097"},{"key":"e_1_3_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1137\/100792779"},{"key":"e_1_3_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00037-007-0220-2"},{"key":"e_1_3_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1995.1017"},{"key":"e_1_3_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFFCS.1999.814607"},{"key":"e_1_3_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1109\/CCC.2001.933879"},{"key":"e_1_3_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1109\/CCC.2007.18"},{"key":"e_1_3_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.4086\/toc.2020.v016a010"},{"key":"e_1_3_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ic.2014.12.003"},{"key":"e_1_3_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-47672-7_22"},{"key":"e_1_3_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1137\/17M1161737"},{"key":"e_1_3_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.4086\/toc.2021.v017a007"},{"key":"e_1_3_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/800061.808737"},{"key":"e_1_3_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/2554797.2554833"},{"key":"e_1_3_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01271266"},{"key":"e_1_3_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1137\/060649057"},{"key":"e_1_3_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1137\/0405044"},{"key":"e_1_3_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1137\/05063235X"},{"key":"e_1_3_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2003.11.002"},{"key":"e_1_3_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2003.07.007"},{"key":"e_1_3_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(96)00019-9"},{"key":"e_1_3_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1007\/s000370050015"},{"key":"e_1_3_2_1_33_1","unstructured":"Troy Lee. 2009. A note on the sign degree of formulas. Available at arxiv:0909.4607  Troy Lee. 2009. A note on the sign degree of formulas. Available at arxiv:0909.4607"},{"key":"e_1_3_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00037-009-0276-2"},{"key":"e_1_3_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02128670"},{"key":"e_1_3_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.TQC.2020.2"},{"key":"e_1_3_2_1_37_1","volume-title":"Papert","author":"Minsky Marvin L.","year":"1969","unstructured":"Marvin L. Minsky and Seymour A . Papert . 1969 . Perceptrons : An Introduction to Computational Geometry. MIT Press , Cambridge, Mass.. Marvin L. Minsky and Seymour A. Papert. 1969. Perceptrons: An Introduction to Computational Geometry. MIT Press, Cambridge, Mass.."},{"key":"e_1_3_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01263419"},{"key":"e_1_3_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00493-010-2173-3"},{"key":"e_1_3_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1006\/inco.1994.1059"},{"key":"e_1_3_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(92)90260-M"},{"key":"e_1_3_2_1_42_1","first-page":"145","article-title":"Quantum communication complexity of symmetric predicates. Izvestiya of the Russian Academy of Sciences","volume":"67","author":"Razborov Alexander A.","year":"2002","unstructured":"Alexander A. Razborov . 2002 . Quantum communication complexity of symmetric predicates. Izvestiya of the Russian Academy of Sciences , Mathematics , 67 (2002), 145 \u2013 159 . Alexander A. Razborov. 2002. Quantum communication complexity of symmetric predicates. Izvestiya of the Russian Academy of Sciences, Mathematics, 67 (2002), 145\u2013159.","journal-title":"Mathematics"},{"key":"e_1_3_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1137\/080744037"},{"key":"e_1_3_2_1_44_1","first-page":"59","article-title":"Communication Lower Bounds Using Dual Polynomials","volume":"95","author":"Sherstov Alexander A.","year":"2008","unstructured":"Alexander A. Sherstov . 2008 . Communication Lower Bounds Using Dual Polynomials . Bulletin of the EATCS , 95 (2008), 59 \u2013 93 . Alexander A. Sherstov. 2008. Communication Lower Bounds Using Dual Polynomials. Bulletin of the EATCS, 95 (2008), 59\u201393.","journal-title":"Bulletin of the EATCS"},{"key":"e_1_3_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00037-009-0274-4"},{"key":"e_1_3_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1137\/08071421X"},{"key":"e_1_3_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1137\/080733644"},{"key":"e_1_3_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1137\/110842661"},{"key":"e_1_3_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1137\/100785260"},{"key":"e_1_3_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.4086\/toc.2013.v009a018"},{"key":"e_1_3_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1145\/2629334"},{"key":"e_1_3_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.1137\/120891587"},{"key":"e_1_3_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.1137\/15M1015704"},{"key":"e_1_3_2_1_54_1","doi-asserted-by":"publisher","DOI":"10.1137\/16M1064477"},{"key":"e_1_3_2_1_55_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00037-021-00211-4"},{"key":"e_1_3_2_1_56_1","doi-asserted-by":"crossref","unstructured":"Alexander A. Sherstov. 2022. The Approximate Degree of DNF and CNF Formulas. In Electronic Colloquium on Computational Complexity (ECCC).  Alexander A. Sherstov. 2022. The Approximate Degree of DNF and CNF Formulas. In Electronic Colloquium on Computational Complexity (ECCC).","DOI":"10.1145\/3519935.3520000"},{"key":"e_1_3_2_1_57_1","doi-asserted-by":"publisher","DOI":"10.1145\/3313276.3316408"},{"key":"e_1_3_2_1_58_1","doi-asserted-by":"publisher","DOI":"10.1109\/18.312168"},{"key":"e_1_3_2_1_59_1","doi-asserted-by":"publisher","DOI":"10.1109\/CCC.1999.766279"},{"key":"e_1_3_2_1_60_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-31594-7_68"},{"key":"e_1_3_2_1_61_1","unstructured":"Robert \u0160palek. 2008. A Dual Polynomial for OR. Available at. arxiv:0803.4516  Robert \u0160palek. 2008. A Dual Polynomial for OR. Available at. arxiv:0803.4516"}],"event":{"name":"STOC '22: 54th Annual ACM SIGACT Symposium on Theory of Computing","sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory"],"location":"Rome Italy","acronym":"STOC '22"},"container-title":["Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3519935.3520000","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3519935.3520000","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T17:49:39Z","timestamp":1750268979000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3519935.3520000"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,6,9]]},"references-count":60,"alternative-id":["10.1145\/3519935.3520000","10.1145\/3519935"],"URL":"https:\/\/doi.org\/10.1145\/3519935.3520000","relation":{},"subject":[],"published":{"date-parts":[[2022,6,9]]},"assertion":[{"value":"2022-06-10","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}