TR19-027 Authors: Mark Bun, Nikhil Mande, Justin Thaler

Publication: 2nd March 2019 03:18

Downloads: 398

Keywords:

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(f)= O(\log n)$, and $UPP(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.