2026-08-17T18:54:03Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:10606 2024-03-06T10:46:15Z ddc:004 open_access

Sign-Rank Can Increase Under Intersection Bun, Mark Mande, Nikhil S. Thaler, Justin Sign rank dimension complexity communication complexity learning theory The communication class UPP^{cc} is a communication analog of the Turing Machine complexity class PP. 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. For a communication problem f, let f wedge f denote the function that evaluates f on two disjoint inputs and outputs the AND of the results. We exhibit a communication problem f with UPP^{cc}(f)= O(log n), and UPP^{cc}(f wedge f) = Theta(log^2 n). This is the first result showing that UPP communication complexity can increase by more than a constant factor under intersection. We view this as a first step toward showing that UPP^{cc}, the class of problems with polylogarithmic-cost UPP communication protocols, is not closed under intersection. Our result shows that the function class consisting of intersections of two majorities on n bits has dimension complexity n^{Omega(log n)}. This matches an upper bound of (Klivans, O'Donnell, 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Mark Bun and Nikhil S. Mande and Justin Thaler 2019 Is Part Of LIPIcs, Volume 132, 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICALP.2019.30 urn:nbn:de:0030-drops-106067 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2019.30 eng https://creativecommons.org/licenses/by/3.0/legalcode