{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T20:10:05Z","timestamp":1750191005492,"version":"3.41.0"},"reference-count":35,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2022,3,4]],"date-time":"2022-03-04T00:00:00Z","timestamp":1646352000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"NSF","award":["CCF-1813930 and CCF-2114116"],"award-info":[{"award-number":["CCF-1813930 and CCF-2114116"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Comput. Theory"],"published-print":{"date-parts":[[2022,3,31]]},"abstract":"\n We prove that the OR function on {-1,1\\}\n \n n<\/jats:italic>\n <\/jats:sup>\n can be pointwise approximated with error \u03b5 by a polynomial of degree\n O<\/jats:italic>\n (\n k<\/jats:italic>\n ) and weight 2\n \n O<\/jats:italic>\n (\n n<\/jats:italic>\n log (1\/\u03b5)\/k)\n <\/jats:sup>\n , for any\n k<\/jats:italic>\n \u2265 \u221a\n n<\/jats:italic>\n log (1\/\u03b5). This result is tight for any\n k<\/jats:italic>\n \u2264 (1-\u03a9 (1))\n n<\/jats:italic>\n . Previous results were either not tight or had \u03b5 = \u03a9 (1). In general, we obtain a tight approximate degree-weight result for any symmetric function. Building on this, we also obtain an approximate degree-weight result for bounded-width CNF. For these two classes no such result was known.\n <\/jats:p>\n \n We prove that the\n \n \\( \\mathsf {OR} \\)<\/jats:tex-math>\n <\/jats:inline-formula>\n function on\n \n \\( \\lbrace -1,1\\rbrace ^n \\)<\/jats:tex-math>\n <\/jats:inline-formula>\n can be pointwise approximated with error\n \n \\( \\epsilon \\)<\/jats:tex-math>\n <\/jats:inline-formula>\n by a polynomial of degree\n \n \\( O(k) \\)<\/jats:tex-math>\n <\/jats:inline-formula>\n and weight\n \n \\( 2^{O(n \\log (1\/\\epsilon) \/k)} \\)<\/jats:tex-math>\n <\/jats:inline-formula>\n , for any\n \n \\( k \\ge \\sqrt {n \\log (1\/\\epsilon)} \\)<\/jats:tex-math>\n <\/jats:inline-formula>\n . This result is tight for any\n \n \\( k \\le (1-\\Omega (1))n \\)<\/jats:tex-math>\n <\/jats:inline-formula>\n . Previous results were either not tight or had\n \n \\( \\epsilon = \\Omega (1) \\)<\/jats:tex-math>\n <\/jats:inline-formula>\n . In general, we obtain a tight approximate degree-weight result for any symmetric function. Building on this, we also obtain an approximate degree-weight result for bounded-width\n \n \\( \\mathsf {CNF} \\)<\/jats:tex-math>\n <\/jats:inline-formula>\n . For these two classes no such result was known.\n <\/jats:p>\n \n One motivation for such results comes from the study of indistinguishability. Two distributions\n \n \\( P \\)<\/jats:tex-math>\n <\/jats:inline-formula>\n ,\n \n \\( Q \\)<\/jats:tex-math>\n <\/jats:inline-formula>\n over\n \n \\( n \\)<\/jats:tex-math>\n <\/jats:inline-formula>\n -bit strings are\n \n \\( (k,\\delta) \\)<\/jats:tex-math>\n <\/jats:inline-formula>\n -indistinguishable if their projections on any\n \n \\( k \\)<\/jats:tex-math>\n <\/jats:inline-formula>\n bits have statistical distance at most\n \n \\( \\delta \\)<\/jats:tex-math>\n <\/jats:inline-formula>\n . The above approximations give values of\n \n \\( (k,\\delta) \\)<\/jats:tex-math>\n <\/jats:inline-formula>\n that suffice to fool\n \n \\( \\mathsf {OR} \\)<\/jats:tex-math>\n <\/jats:inline-formula>\n , symmetric functions, and bounded-width\n \n \\( \\mathsf {CNF} \\)<\/jats:tex-math>\n <\/jats:inline-formula>\n , and the first result is tight for all\n \n \\( k \\)<\/jats:tex-math>\n <\/jats:inline-formula>\n while the second result is tight for\n \n \\( k \\le (1-\\Omega (1))n \\)<\/jats:tex-math>\n <\/jats:inline-formula>\n . We also show that any two\n \n \\( (k, \\delta) \\)<\/jats:tex-math>\n <\/jats:inline-formula>\n -indistinguishable distributions are\n \n \\( O(n^{k\/2}\\delta) \\)<\/jats:tex-math>\n <\/jats:inline-formula>\n -close to two distributions that are\n \n \\( (k,0) \\)<\/jats:tex-math>\n <\/jats:inline-formula>\n -indistinguishable, improving the previous bound of\n \n \\( O(n)^k \\delta \\)<\/jats:tex-math>\n <\/jats:inline-formula>\n . Finally, we present proofs of some known approximate degree lower bounds in the language of indistinguishability, which we find more intuitive.\n <\/jats:p>","DOI":"10.1145\/3492338","type":"journal-article","created":{"date-parts":[[2022,3,4]],"date-time":"2022-03-04T10:12:34Z","timestamp":1646388754000},"page":"1-26","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["Approximate Degree, Weight, and Indistinguishability"],"prefix":"10.1145","volume":"14","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-0249-4203","authenticated-orcid":false,"given":"Xuangui","family":"Huang","sequence":"first","affiliation":[{"name":"Northeastern University, Boston, MA, USA"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-6091-1824","authenticated-orcid":false,"given":"Emanuele","family":"Viola","sequence":"additional","affiliation":[{"name":"Northeastern University, Boston, MA, USA"}]}],"member":"320","published-online":{"date-parts":[[2022,3,4]]},"reference":[{"key":"e_1_3_2_2_2","first-page":"338","volume-title":"Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques","author":"Ada Anil","year":"2012","unstructured":"Anil Ada, Omar Fawzi, and Hamed Hatami. 2012. Spectral norm of symmetric functions. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, Anupam Gupta, Klaus Jansen, Jos\u00e9 Rolim, and Rocco Servedio (Eds.). Springer, Berlin, 338\u2013349."},{"key":"e_1_3_2_3_2","unstructured":"Anil Ada Omar Fawzi and Raghav Kulkarni. 2017. On the spectral properties of symmetric functions. arXiv:1704.03176 [cs.CC]"},{"key":"e_1_3_2_4_2","doi-asserted-by":"publisher","DOI":"10.1016\/S0020-0190(03)00359-4"},{"key":"e_1_3_2_5_2","doi-asserted-by":"publisher","DOI":"10.5555\/2231016.2231027"},{"key":"e_1_3_2_6_2","article-title":"Approximate Degree of AND via Fourier Analysis","author":"Bogdanov Andrej","year":"2018","unstructured":"Andrej Bogdanov. 2018. Approximate Degree of AND via Fourier Analysis. Electronic Colloquium on Computational Complexity, TR18-197.","journal-title":"Electronic Colloquium on Computational Complexity, TR18-197"},{"key":"e_1_3_2_7_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-53015-3_21"},{"key":"e_1_3_2_8_2","first-page":"71:1\u201371:21","volume-title":"Proceedings of the International Conference on Approximation Algorithms for Combinatorial Optimization Problems\/International Conference on Randomization and Computation (APPROX\/RANDOM\u201919)","author":"Bogdanov Andrej","year":"2019","unstructured":"Andrej Bogdanov, Nikhil S. Mande, Justin Thaler, and Christopher Williamson. 2019. Approximate degree, secret sharing, and concentration phenomena. In Proceedings of the International Conference on Approximation Algorithms for Combinatorial Optimization Problems\/International Conference on Randomization and Computation (APPROX\/RANDOM\u201919), Leibniz International Proceedings in Informatics (LIPIcs), Vol. 145, Dimitris Achlioptas and L\u00e1szl\u00f3 A. V\u00e9gh (Eds.). Schloss Dagstuhl\u2013Leibniz-Zentrum fuer Informatik, Dagstuhl, Germany, 71:1\u201371:21."},{"key":"e_1_3_2_9_2","series-title":"Proceedings of the 44th International Colloquium on Automata, Languages, and Programming (ICALP\u201917),","first-page":"53:1\u201353:11","volume":"80","author":"Bogdanov Andrej","year":"2017","unstructured":"Andrej Bogdanov and Christopher Williamson. 2017. Approximate bounded indistinguishability. In Proceedings of the 44th International Colloquium on Automata, Languages, and Programming (ICALP\u201917),Leibniz International Proceedings in Informatics (LIPIcs), Vol. 80, Ioannis Chatzigiannakis, Piotr Indyk, Fabian Kuhn, and Anca Muscholl (Eds.). Schloss Dagstuhl\u2013Leibniz-Zentrum fuer Informatik, Dagstuhl, Germany, 53:1\u201353:11."},{"key":"e_1_3_2_10_2","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2017.71"},{"key":"e_1_3_2_11_2","doi-asserted-by":"publisher","DOI":"10.1109\/SFFCS.1999.814607"},{"key":"e_1_3_2_12_2","first-page":"120","volume-title":"Proceedings of the 16th Annual Conference on Computational Complexity (CCC\u201901)","author":"Buhrman Harry","year":"2001","unstructured":"Harry Buhrman and Ronald de Wolf. 2001. Communication complexity lower bounds by polynomials. In Proceedings of the 16th Annual Conference on Computational Complexity (CCC\u201901). IEEE Computer Society, Washington, DC, 120\u2013130."},{"key":"e_1_3_2_13_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00224-006-1313-z"},{"key":"e_1_3_2_14_2","doi-asserted-by":"publisher","DOI":"10.1145\/3188745.3188784"},{"key":"e_1_3_2_15_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-39206-1_26"},{"key":"e_1_3_2_16_2","first-page":"268","volume-title":"Automata, Languages, and Programming","author":"Bun Mark","year":"2015","unstructured":"Mark Bun and Justin Thaler. 2015. Hardness amplification and the approximate degree of constant-depth circuits. In Automata, Languages, and Programming, Magn\u00fas M. Halld\u00f3rsson, Kazuo Iwama, Naoki Kobayashi, and Bettina Speckmann (Eds.). Springer, Berlin, 268\u2013280."},{"key":"e_1_3_2_17_2","first-page":"1","volume-title":"Proceedings of the 58th IEEE Annual Symposium on Foundations of Computer Science (FOCS\u201917)","author":"Bun Mark","year":"2017","unstructured":"Mark Bun and Justin Thaler. 2017. A nearly optimal lower bound on the approximate degree of \\( \\mathsf {AC}^0 \\) . In Proceedings of the 58th IEEE Annual Symposium on Foundations of Computer Science (FOCS\u201917). IEEE Computer Society, Los Alamitos, CA, 1\u201312."},{"key":"e_1_3_2_18_2","doi-asserted-by":"publisher","DOI":"10.1145\/2554797.2554833"},{"key":"e_1_3_2_19_2","doi-asserted-by":"publisher","DOI":"10.1145\/3313276.3316353"},{"key":"e_1_3_2_20_2","volume-title":"Introduction to Approximation Theory (2nd ed.)","author":"Cheney E. W.","year":"1982","unstructured":"E. W. Cheney. 1982. Introduction to Approximation Theory (2nd ed.). Chelsea Pub. Co., New York, N.Y.81067708"},{"key":"e_1_3_2_21_2","doi-asserted-by":"publisher","DOI":"10.1111\/j.1751-5823.2002.tb00178.x"},{"key":"e_1_3_2_22_2","doi-asserted-by":"publisher","DOI":"10.1080\/01621459.1963.10500830"},{"key":"e_1_3_2_23_2","article-title":"Approximate Degree-Weight and Indistinguishability","author":"Huang Xuangui","year":"2019","unstructured":"Xuangui Huang and Emanuele Viola. 2019. Approximate Degree-Weight and Indistinguishability. Electronic Colloquium on Computational Complexity, TR19-085.","journal-title":"Electronic Colloquium on Computational Complexity, TR19-085"},{"key":"e_1_3_2_24_2","doi-asserted-by":"publisher","DOI":"10.5555\/1248547.1248567"},{"key":"e_1_3_2_25_2","doi-asserted-by":"publisher","DOI":"10.1137\/0222053"},{"key":"e_1_3_2_26_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF01263419"},{"key":"e_1_3_2_27_2","doi-asserted-by":"publisher","DOI":"10.5555\/2683783"},{"key":"e_1_3_2_28_2","series-title":"Proceedings of the International Conference on Approximation Algorithms for Combinatorial Optimization Problems\/International Conference on Randomization and Computation (APPROX\/RANDOM\u201918),","first-page":"54:1\u201354:19","volume":"116","author":"O\u2019Donnell Ryan","year":"2018","unstructured":"Ryan O\u2019Donnell and Yu Zhao. 2018. On closeness to k-wise uniformity. In Proceedings of the International Conference on Approximation Algorithms for Combinatorial Optimization Problems\/International Conference on Randomization and Computation (APPROX\/RANDOM\u201918),Leibniz International Proceedings in Informatics (LIPIcs), Vol. 116, Eric Blais, Klaus Jansen, Jos\u00e9 D. P. Rolim, and David Steurer (Eds.). Schloss Dagstuhl\u2013Leibniz-Zentrum fuer Informatik, Dagstuhl, Germany, 54:1\u201354:19."},{"key":"e_1_3_2_29_2","doi-asserted-by":"publisher","DOI":"10.1145\/129712.129758"},{"key":"e_1_3_2_30_2","series-title":"Proceedings of the 25th Annual Conference on Learning Theory","first-page":"14.1\u201314.19","volume":"23","author":"Servedio Rocco A.","year":"2012","unstructured":"Rocco A. Servedio, Li-Yang Tan, and Justin Thaler. 2012. Attribute-efficient learning and weight-degree tradeoffs for polynomial threshold functions. In Proceedings of the 25th Annual Conference on Learning Theory, Proceedings of Machine Learning Research, Vol. 23, Shie Mannor, Nathan Srebro, and Robert C. Williamson (Eds.). PMLR, Edinburgh, Scotland, 14.1\u201314.19."},{"key":"e_1_3_2_31_2","doi-asserted-by":"publisher","DOI":"10.1109\/CCC.2008.18"},{"key":"e_1_3_2_32_2","doi-asserted-by":"publisher","DOI":"10.1137\/110842661"},{"key":"e_1_3_2_33_2","doi-asserted-by":"publisher","DOI":"10.4086\/toc.2013.v009a020"},{"key":"e_1_3_2_34_2","doi-asserted-by":"publisher","DOI":"10.1137\/100785260"},{"key":"e_1_3_2_35_2","doi-asserted-by":"publisher","DOI":"10.1145\/3188745.3188958"},{"key":"e_1_3_2_36_2","unstructured":"Emanuele Viola. 2017. Special Topics in Complexity Theory. ECCC Lecture Notes. Retrieved December 28 2017 fromhttp:\/\/www.ccs.neu.edu\/home\/viola\/classes\/spepf17.html."}],"container-title":["ACM Transactions on Computation Theory"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3492338","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3492338","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3492338","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T19:31:09Z","timestamp":1750188669000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3492338"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,3,4]]},"references-count":35,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2022,3,31]]}},"alternative-id":["10.1145\/3492338"],"URL":"https:\/\/doi.org\/10.1145\/3492338","relation":{},"ISSN":["1942-3454","1942-3462"],"issn-type":[{"type":"print","value":"1942-3454"},{"type":"electronic","value":"1942-3462"}],"subject":[],"published":{"date-parts":[[2022,3,4]]},"assertion":[{"value":"2020-08-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2021-09-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2022-03-04","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}