  The communication class $\mathbf{UPP}^{\text{cc}}$ is a communication analog
of the Turing Machine complexity class $\mathbf{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 $\mathbf{UPP}(f)= O(\log n)$, and
$\mathbf{UPP}(f \wedge f) = \Theta(\log^2 n)$. This is the first result showing
that $\mathbf{UPP}$ communication complexity can increase by more than a
constant factor under intersection. We view this as a first step toward showing
that $\mathbf{UPP}^{\text{cc}}$, the class of problems with
polylogarithmic-cost $\mathbf{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.

Computational Complexity