{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,4]],"date-time":"2026-04-04T05:58:43Z","timestamp":1775282323303,"version":"3.50.1"},"reference-count":33,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2021,9,1]],"date-time":"2021-09-01T00:00:00Z","timestamp":1630454400000},"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":["ACM Trans. Comput. Theory"],"published-print":{"date-parts":[[2021,12,31]]},"abstract":"<jats:p>\n            The communication class\n            <jats:bold>UPP<\/jats:bold>\n            <jats:sup>cc<\/jats:sup>\n            is a communication analog of the Turing Machine complexity class\n            <jats:bold>PP<\/jats:bold>\n            . It is characterized by a matrix-analytic complexity measure called sign-rank (also called dimension complexity), and is essentially the most powerful communication class against which we know how to prove lower bounds.\n          <\/jats:p>\n          <jats:p>\n            For a communication problem\n            <jats:italic>f<\/jats:italic>\n            , let\n            <jats:italic>f<\/jats:italic>\n            \u2227\n            <jats:italic>f<\/jats:italic>\n            denote the function that evaluates\n            <jats:italic>f<\/jats:italic>\n            on two disjoint inputs and outputs the AND of the results. We exhibit a communication problem\n            <jats:italic>f<\/jats:italic>\n            with\n            <jats:bold>UPP<\/jats:bold>\n            <jats:sup>cc<\/jats:sup>\n            (\n            <jats:italic>f<\/jats:italic>\n            ) =\n            <jats:italic>O<\/jats:italic>\n            (log\n            <jats:italic>n<\/jats:italic>\n            ), and\n            <jats:bold>UPP<\/jats:bold>\n            <jats:sup>cc<\/jats:sup>\n            (\n            <jats:italic>f<\/jats:italic>\n            \u2227\n            <jats:italic>f<\/jats:italic>\n            ) = \u0398 (log\n            <jats:sup>2<\/jats:sup>\n            <jats:italic>n<\/jats:italic>\n            ). This is the first result showing that\n            <jats:bold>UPP<\/jats:bold>\n            communication complexity can increase by more than a constant factor under intersection. We view this as a first step toward showing that\n            <jats:bold>UPP<\/jats:bold>\n            <jats:sup>cc<\/jats:sup>\n            , the class of problems with polylogarithmic-cost\n            <jats:bold>UPP<\/jats:bold>\n            communication protocols, is not closed under intersection.\n          <\/jats:p>\n          <jats:p>\n            Our result shows that the function class consisting of intersections of two majorities on\n            <jats:italic>n<\/jats:italic>\n            bits has dimension complexity\n            <jats:italic>n<\/jats:italic>\n            Omega\n            <jats:sup>\n              \u03a9(log\n              <jats:italic>n<\/jats:italic>\n              )\n            <\/jats:sup>\n            . This matches an upper bound of (Klivans, O\u2019Donnell, and Servedio, FOCS 2002), who used it to give a quasipolynomial time algorithm for PAC learning intersections of polylogarithmically many majorities. Hence, fundamentally new techniques will be needed to learn this class of functions in polynomial time.\n          <\/jats:p>","DOI":"10.1145\/3470863","type":"journal-article","created":{"date-parts":[[2021,9,1]],"date-time":"2021-09-01T19:28:46Z","timestamp":1630524526000},"page":"1-17","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":1,"title":["Sign-rank Can Increase under Intersection"],"prefix":"10.1145","volume":"13","author":[{"given":"Mark","family":"Bun","sequence":"first","affiliation":[{"name":"Boston University, Boston, MA, USA"}]},{"given":"Nikhil S.","family":"Mande","sequence":"additional","affiliation":[{"name":"CWI, Amsterdam, The Netherlands"}]},{"given":"Justin","family":"Thaler","sequence":"additional","affiliation":[{"name":"Georgetown University, Washington, USA"}]}],"member":"320","published-online":{"date-parts":[[2021,9]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1985.30"},{"key":"e_1_2_1_2_1","volume-title":"Proceedings of the 29th Conference on Learning Theory (COLT). JMLR.org, 47\u201380","author":"Alon Noga","year":"2016","unstructured":"Noga Alon , Shay Moran , and Amir Yehudayoff . 2016 . Sign rank versus VC dimension . In Proceedings of the 29th Conference on Learning Theory (COLT). JMLR.org, 47\u201380 . Retrieved from http:\/\/jmlr.org\/proceedings\/papers\/v49\/alon16.html. Noga Alon, Shay Moran, and Amir Yehudayoff. 2016. Sign rank versus VC dimension. In Proceedings of the 29th Conference on Learning Theory (COLT). JMLR.org, 47\u201380. Retrieved from http:\/\/jmlr.org\/proceedings\/papers\/v49\/alon16.html."},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.5555\/1958033.1958051"},{"key":"e_1_2_1_4_1","volume-title":"Proceedings of the 27th Symposium on Foundations of Computer Science (FOCS). IEEE Computer Society, 337\u2013347","author":"Babai L\u00e1szl\u00f3","year":"1986","unstructured":"L\u00e1szl\u00f3 Babai , Peter Frankl , and Janos Simon . 1986 . Complexity classes in communication complexity theory (preliminary version) . In Proceedings of the 27th Symposium on Foundations of Computer Science (FOCS). IEEE Computer Society, 337\u2013347 . DOI:DOI:https:\/\/doi.org\/10.1109\/SFCS.1986.15 10.1109\/SFCS.1986.15 L\u00e1szl\u00f3 Babai, Peter Frankl, and Janos Simon. 1986. Complexity classes in communication complexity theory (preliminary version). In Proceedings of the 27th Symposium on Foundations of Computer Science (FOCS). IEEE Computer Society, 337\u2013347. DOI:DOI:https:\/\/doi.org\/10.1109\/SFCS.1986.15"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1995.1017"},{"key":"e_1_2_1_6_1","volume-title":"Proceedings of the Conference On Learning Theory (COLT). PMLR, 876\u2013917","author":"Bhattacharyya Arnab","year":"2018","unstructured":"Arnab Bhattacharyya , Suprovat Ghoshal , and Rishi Saket . 2018 . Hardness of learning noisy halfspaces using polynomial thresholds . In Proceedings of the Conference On Learning Theory (COLT). PMLR, 876\u2013917 . Retrieved from http:\/\/proceedings.mlr.press\/v75\/bhattacharyya18a.html. Arnab Bhattacharyya, Suprovat Ghoshal, and Rishi Saket. 2018. Hardness of learning noisy halfspaces using polynomial thresholds. In Proceedings of the Conference On Learning Theory (COLT). PMLR, 876\u2013917. Retrieved from http:\/\/proceedings.mlr.press\/v75\/bhattacharyya18a.html."},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2017.71"},{"key":"e_1_2_1_8_1","first-page":"1","article-title":"Sign-rank can increase under intersection. In Proceedings of the 46th International Colloquium on Automata, Languages, and Programming (ICALP)","volume":"30","author":"Bun Mark","year":"2019","unstructured":"Mark Bun , Nikhil S. Mande , and Justin Thaler . 2019 . Sign-rank can increase under intersection. In Proceedings of the 46th International Colloquium on Automata, Languages, and Programming (ICALP) . Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik , 30 : 1 \u2013 30 :14. DOI:DOI:https:\/\/doi.org\/10.4230\/LIPIcs.ICALP.2019.30 10.4230\/LIPIcs.ICALP.2019.30 Mark Bun, Nikhil S. Mande, and Justin Thaler. 2019. Sign-rank can increase under intersection. In Proceedings of the 46th International Colloquium on Automata, Languages, and Programming (ICALP). Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, 30:1\u201330:14. DOI:DOI:https:\/\/doi.org\/10.4230\/LIPIcs.ICALP.2019.30","journal-title":"Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik"},{"key":"e_1_2_1_9_1","first-page":"1","article-title":"Improved bounds on the sign-rank of AC. In Proceedings of the 43rd International Colloquium on Automata, Languages, and Programming (ICALP)","volume":"37","author":"Bun Mark","year":"2016","unstructured":"Mark Bun and Justin Thaler . 2016 . Improved bounds on the sign-rank of AC. In Proceedings of the 43rd International Colloquium on Automata, Languages, and Programming (ICALP) . Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik , 37 : 1 \u2013 37 :14. DOI:DOI:https:\/\/doi.org\/10.4230\/LIPIcs.ICALP.2016.37 10.4230\/LIPIcs.ICALP.2016.37 Mark Bun and Justin Thaler. 2016. Improved bounds on the sign-rank of AC. In Proceedings of the 43rd International Colloquium on Automata, Languages, and Programming (ICALP). Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, 37:1\u201337:14. DOI:DOI:https:\/\/doi.org\/10.4230\/LIPIcs.ICALP.2016.37","journal-title":"Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik"},{"key":"e_1_2_1_10_1","first-page":"1","article-title":"The large-error approximate degree of AC. In Proceedings of the Conference on Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX\/RANDOM)","volume":"55","author":"Bun Mark","year":"2019","unstructured":"Mark Bun and Justin Thaler . 2019 . The large-error approximate degree of AC. In Proceedings of the Conference on Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX\/RANDOM) . Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik , 55 : 1 \u2013 55 :16. DOI:DOI:https:\/\/doi.org\/10.4230\/LIPIcs.APPROX-RANDOM.2019.55 10.4230\/LIPIcs.APPROX-RANDOM.2019.55 Mark Bun and Justin Thaler. 2019. The large-error approximate degree of AC. In Proceedings of the Conference on Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX\/RANDOM). Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, 55:1\u201355:16. DOI:DOI:https:\/\/doi.org\/10.4230\/LIPIcs.APPROX-RANDOM.2019.55","journal-title":"Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik"},{"key":"e_1_2_1_11_1","volume-title":"Proceedings of the 59th IEEE Symposium on Foundations of Computer Science (FOCS). IEEE Computer Society, 47\u201358","author":"Chattopadhyay Arkadev","year":"2018","unstructured":"Arkadev Chattopadhyay and Nikhil S. Mande . 2018. A short list of equalities induces large sign rank . In Proceedings of the 59th IEEE Symposium on Foundations of Computer Science (FOCS). IEEE Computer Society, 47\u201358 . DOI:DOI:https:\/\/doi.org\/10.1109\/FOCS. 2018 .00014 10.1109\/FOCS.2018.00014 Arkadev Chattopadhyay and Nikhil S. Mande. 2018. A short list of equalities induces large sign rank. In Proceedings of the 59th IEEE Symposium on Foundations of Computer Science (FOCS). IEEE Computer Society, 47\u201358. DOI:DOI:https:\/\/doi.org\/10.1109\/FOCS.2018.00014"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2006.51"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(02)00019-3"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.5555\/646839.708661"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2005.10.015"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00037-018-0175-5"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2017.21"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00037-018-0166-6"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/293347.293351"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2010.06.010"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2003.11.002"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2003.07.007"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2008.07.008"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00493-007-2160-5"},{"key":"e_1_2_1_25_1","unstructured":"Marvin Minsky and Seymour Papert. 1969. Perceptrons. The MIT Press.  Marvin Minsky and Seymour Papert. 1969. Perceptrons. The MIT Press."},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(86)90046-2"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.5555\/1958016.1958022"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1137\/080733644"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00493-011-2580-0"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1137\/100785260"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00493-013-2759-7"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1137\/15M1015704"},{"key":"e_1_2_1_33_1","volume-title":"Proceedings of the 51st ACM SIGACT Symposium on Theory of Computing (STOC). ACM, 401\u2013412","author":"Alexander","unstructured":"Alexander A. Sherstov and Pei Wu. 2019. Near-optimal lower bounds on the threshold degree and sign-rank of AC . In Proceedings of the 51st ACM SIGACT Symposium on Theory of Computing (STOC). ACM, 401\u2013412 . DOI:DOI:https:\/\/doi.org\/10.1145\/3313276.3316408 10.1145\/3313276.3316408 Alexander A. Sherstov and Pei Wu. 2019. Near-optimal lower bounds on the threshold degree and sign-rank of AC. In Proceedings of the 51st ACM SIGACT Symposium on Theory of Computing (STOC). ACM, 401\u2013412. DOI:DOI:https:\/\/doi.org\/10.1145\/3313276.3316408"}],"container-title":["ACM Transactions on Computation Theory"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3470863","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3470863","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T20:18:55Z","timestamp":1750191535000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3470863"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,9]]},"references-count":33,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2021,12,31]]}},"alternative-id":["10.1145\/3470863"],"URL":"https:\/\/doi.org\/10.1145\/3470863","relation":{},"ISSN":["1942-3454","1942-3462"],"issn-type":[{"value":"1942-3454","type":"print"},{"value":"1942-3462","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,9]]},"assertion":[{"value":"2020-05-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2021-04-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2021-09-01","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}