{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T04:29:33Z","timestamp":1750220973860,"version":"3.41.0"},"publisher-location":"New York, NY, USA","reference-count":51,"publisher":"ACM","license":[{"start":{"date-parts":[[2019,6,23]],"date-time":"2019-06-23T00:00:00Z","timestamp":1561248000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CCF- 1814947"],"award-info":[{"award-number":["CCF- 1814947"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000879","name":"Alfred P. Sloan Foundation","doi-asserted-by":"publisher","award":["Research Fellowship"],"award-info":[{"award-number":["Research Fellowship"]}],"id":[{"id":"10.13039\/100000879","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2019,6,23]]},"DOI":"10.1145\/3313276.3316408","type":"proceedings-article","created":{"date-parts":[[2019,6,20]],"date-time":"2019-06-20T12:19:08Z","timestamp":1561033148000},"page":"401-412","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":5,"title":["Near-optimal lower bounds on the threshold degree and sign-rank of AC\n            <sup>0<\/sup>"],"prefix":"10.1145","author":[{"given":"Alexander A.","family":"Sherstov","sequence":"first","affiliation":[{"name":"University of California at Los Angeles, USA"}]},{"given":"Pei","family":"Wu","sequence":"additional","affiliation":[{"name":"University of California at Los Angeles, USA"}]}],"member":"320","published-online":{"date-parts":[[2019,6,23]]},"reference":[{"key":"e_1_3_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/1008731.1008735"},{"key":"e_1_3_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.5555\/1958033.1958051"},{"key":"e_1_3_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01215346"},{"key":"e_1_3_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1986.15"},{"key":"e_1_3_2_1_5_1","unstructured":"Paul Beame and Trinh Huynh. 2012.  Paul Beame and Trinh Huynh. 2012."},{"key":"e_1_3_2_1_6_1","volume-title":"484\u2013518","author":"Complexity Multiparty Communication","year":"2012","unstructured":"Multiparty Communication Complexity and Threshold Circuit Size of AC 0. SIAM J. Comput . 41, 3 ( 2012 ), 484\u2013518 . Multiparty Communication Complexity and Threshold Circuit Size of AC 0. SIAM J. Comput. 41, 3 (2012), 484\u2013518."},{"key":"e_1_3_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1109\/CCC.2007.18"},{"key":"e_1_3_2_1_8_1","doi-asserted-by":"crossref","unstructured":"Mark Bun Robin Kothari and Justin Thaler. 2018. The polynomial method strikes back: Tight quantum query bounds via dual polynomials. In STOC. 297\u2013310.  Mark Bun Robin Kothari and Justin Thaler. 2018. The polynomial method strikes back: Tight quantum query bounds via dual polynomials. In STOC. 297\u2013310.","DOI":"10.1145\/3188745.3188784"},{"key":"e_1_3_2_1_9_1","doi-asserted-by":"crossref","unstructured":"Mark Bun and Justin Thaler. 2015. Hardness Amplification and the Approximate Degree of Constant-Depth Circuits. In ICALP. 268\u2013280.  Mark Bun and Justin Thaler. 2015. Hardness Amplification and the Approximate Degree of Constant-Depth Circuits. In ICALP. 268\u2013280.","DOI":"10.1007\/978-3-662-47672-7_22"},{"key":"e_1_3_2_1_10_1","unstructured":"Mark Bun and Justin Thaler. 2016.  Mark Bun and Justin Thaler. 2016."},{"key":"e_1_3_2_1_11_1","unstructured":"Approximate Degree and the Complexity of Depth Three Circuits. In Electronic Colloquium on Computational Complexity (ECCC). Report TR16-121.  Approximate Degree and the Complexity of Depth Three Circuits. In Electronic Colloquium on Computational Complexity (ECCC). Report TR16-121."},{"key":"e_1_3_2_1_12_1","first-page":"1","article-title":"Improved Bounds on the Sign-Rank of AC 0","volume":"37","author":"Bun Mark","year":"2016","unstructured":"Mark Bun and Justin Thaler . 2016 . Improved Bounds on the Sign-Rank of AC 0 . In ICALP. 37 : 1 \u2013 37 :14. Mark Bun and Justin Thaler. 2016. Improved Bounds on the Sign-Rank of AC 0. In ICALP. 37:1\u201337:14.","journal-title":"ICALP."},{"key":"e_1_3_2_1_13_1","unstructured":"Mark Bun and Justin Thaler. 2017.  Mark Bun and Justin Thaler. 2017."},{"key":"e_1_3_2_1_14_1","unstructured":"A Nearly Optimal Lower Bound on the Approximate Degree of AC 0. In FOCS. 1\u201312.  A Nearly Optimal Lower Bound on the Approximate Degree of AC 0. In FOCS. 1\u201312."},{"key":"e_1_3_2_1_16_1","doi-asserted-by":"crossref","unstructured":"Arkadev Chattopadhyay. 2007. Discrepancy and the power of bottom fan-in in depth-three circuits. In FOCS. 449\u2013458.  Arkadev Chattopadhyay. 2007. Discrepancy and the power of bottom fan-in in depth-three circuits. In FOCS. 449\u2013458.","DOI":"10.1109\/FOCS.2007.30"},{"key":"e_1_3_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(02)00019-3"},{"key":"e_1_3_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.5555\/646839.708661"},{"key":"e_1_3_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2003.07.007"},{"key":"e_1_3_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.5555\/1248547.1248567"},{"key":"e_1_3_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(96)00019-9"},{"key":"e_1_3_2_1_22_1","unstructured":"Eyal Kushilevitz and Noam Nisan. 1997.  Eyal Kushilevitz and Noam Nisan. 1997."},{"key":"e_1_3_2_1_23_1","unstructured":"Communication complexity. Cambridge University Press.  Communication complexity. Cambridge University Press."},{"key":"e_1_3_2_1_24_1","unstructured":"Troy Lee. 2009.  Troy Lee. 2009."},{"key":"e_1_3_2_1_25_1","unstructured":"A note on the sign degree of formulas. Available at http: \/\/arxiv.org\/abs\/0909.4607.  A note on the sign degree of formulas. Available at http: \/\/arxiv.org\/abs\/0909.4607."},{"key":"e_1_3_2_1_26_1","volume-title":"Papert","author":"Minsky Marvin L.","year":"1969","unstructured":"Marvin L. Minsky and Seymour A . Papert . 1969 . Marvin L. Minsky and Seymour A. Papert. 1969."},{"volume-title":"An Introduction to Computational Geometry","author":"Perceptrons","key":"e_1_3_2_1_27_1","unstructured":"Perceptrons : An Introduction to Computational Geometry . MIT Press, Cambridge , Mass . Perceptrons: An Introduction to Computational Geometry. MIT Press, Cambridge, Mass."},{"key":"e_1_3_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01263419"},{"key":"e_1_3_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00493-010-2173-3"},{"key":"e_1_3_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/129712.129758"},{"key":"e_1_3_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(86)90046-2"},{"key":"e_1_3_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.5555\/1958016.1958022"},{"key":"e_1_3_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00037-008-0242-4"},{"key":"e_1_3_2_1_34_1","unstructured":"Alexander A. Sherstov. 2009.  Alexander A. Sherstov. 2009."},{"key":"e_1_3_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1137\/08071421X"},{"key":"e_1_3_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00037-009-0285-1"},{"key":"e_1_3_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1137\/080733644"},{"key":"e_1_3_2_1_38_1","unstructured":"Preliminary version in STOC 2008.  Preliminary version in STOC 2008."},{"key":"e_1_3_2_1_39_1","unstructured":"Alexander A. Sherstov. 2012.  Alexander A. Sherstov. 2012."},{"key":"e_1_3_2_1_40_1","volume-title":"1122\u20131165","author":"Product Strong Direct","year":"2012","unstructured":"Strong Direct Product Theorems for Quantum Communication and Query Complexity . SIAM J. Comput . 41, 5 ( 2012 ), 1122\u20131165 . Strong Direct Product Theorems for Quantum Communication and Query Complexity. SIAM J. Comput. 41, 5 (2012), 1122\u20131165."},{"key":"e_1_3_2_1_41_1","unstructured":"Preliminary version in STOC 2011.  Preliminary version in STOC 2011."},{"key":"e_1_3_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1137\/100785260"},{"key":"e_1_3_2_1_43_1","unstructured":"Alexander A. Sherstov. 2013.  Alexander A. Sherstov. 2013."},{"key":"e_1_3_2_1_44_1","volume-title":"Theory of Computing 9","author":"Making","year":"2013","unstructured":"Making polynomials robust to noise. Theory of Computing 9 ( 2013 ), 593\u2013615. Preliminary version in STOC , 2012. Making polynomials robust to noise. Theory of Computing 9 (2013), 593\u2013615. Preliminary version in STOC, 2012."},{"key":"e_1_3_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00493-013-2759-7"},{"key":"e_1_3_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1145\/2629334"},{"key":"e_1_3_2_1_48_1","unstructured":"Alexander A. Sherstov. 2015.  Alexander A. Sherstov. 2015."},{"key":"e_1_3_2_1_49_1","unstructured":"The Power of Asymmetry in Constant-Depth Circuits. In FOCS. 431\u2013450.  The Power of Asymmetry in Constant-Depth Circuits. In FOCS. 431\u2013450."},{"key":"e_1_3_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1137\/120891587"},{"key":"e_1_3_2_1_51_1","volume-title":"Sherstov and Pei Wu","author":"Alexander","year":"2019","unstructured":"Alexander A. Sherstov and Pei Wu . 2019 . Alexander A. Sherstov and Pei Wu. 2019."},{"key":"e_1_3_2_1_52_1","unstructured":"Near-optimal lower bounds on the threshold degree and sign-rank of AC 0. In Electronic Colloquium on Computational Complexity (ECCC). Report TR19-003.  Near-optimal lower bounds on the threshold degree and sign-rank of AC 0. In Electronic Colloquium on Computational Complexity (ECCC). Report TR19-003."},{"key":"e_1_3_2_1_53_1","unstructured":"Justin Thaler. 2016.  Justin Thaler. 2016."}],"event":{"name":"STOC '19: 51st Annual ACM SIGACT Symposium on the Theory of Computing","sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory"],"location":"Phoenix AZ USA","acronym":"STOC '19"},"container-title":["Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3313276.3316408","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3313276.3316408","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3313276.3316408","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T23:54:33Z","timestamp":1750204473000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3313276.3316408"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,6,23]]},"references-count":51,"alternative-id":["10.1145\/3313276.3316408","10.1145\/3313276"],"URL":"https:\/\/doi.org\/10.1145\/3313276.3316408","relation":{},"subject":[],"published":{"date-parts":[[2019,6,23]]},"assertion":[{"value":"2019-06-23","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}