Communication complexity class UPPcc is not closed under intersection
UPP$^{\text{cc}}$ is Not Closed Under Intersection
Computational Complexity
Summary
This paper studies a particular way to measure the complexity of communication problems represented by matrices of +1 and -1 values. The authors find an explicit example showing that when you combine two such problems with a logical AND (intersection), the complexity can grow much more than expected. This means a certain class of communication problems, called UPPcc, does not behave neatly when you take intersections of problems. They use mathematical tools linking geometric representations and polynomials to prove this.
What this means in practice
- •For communication system designers: Assess limits on composing unbounded-error communication protocols through Boolean intersections.
- •For complexity theory tool developers: Guide development of lower bound techniques by illustrating limits of sign rank under matrix conjunction.
A theory result. No direct application yet.
Authors
Mark Bun, Mandar Juvekar
Abstract
The sign rank of a ${\pm 1}$-valued matrix $A$ is the minimum rank of a real matrix that agrees with $A$ entrywise in sign. For every sufficiently large $d$, we give an explicit matrix $A$ with $2^{Θ(d^2)}$ rows and columns and sign rank $Θ(d)$ such that $A \land A$ has sign rank $2^{Θ(d)}$. Here, $A \land A$ is the communication matrix of the problem obtained by evaluating $A$ on disjoint inputs and taking the conjunction of the results. As the logarithm of sign rank characterizes unbounded-error communication complexity, this implies that the communication class $\mathsf{UPP}^{\mathsf{cc}}$ is not closed under intersection. The starting point for our lower bound is Forster's method, which relates the sign rank of a matrix to the average margin of representations of its rows and columns by points and halfspaces. We study a continuous analog for conjunctions of inner-product sign tests on the unit sphere. Rotational symmetry connects this problem to polynomial sign representations, yielding an exponentially small upper bound on the average margin. This bound holds even when sign constraints are relaxed near the sign tests' decision boundary, allowing us to transfer it to explicit finite sign matrices arising from intersections of integer halfspaces.