TITLE:  The Pattern Matrix Method for Lower Bounds on Bounded-Error Communication

AUTHOR: Alexander A. Sherstov

ABSTRACT:

We develop a novel and powerful technique for lower bounds on
bounded-error communication complexity, the pattern matrix method.
It works not only in the classical model but also in the quantum
model, regardless of prior entanglement.  Specifically, fix an
arbitrary function f:{0,1}^{n/4}->{0,1} and let A be the matrix
whose columns are each an application of f to some subset of the
variables x_1,x_2,...,x_n. We prove that A has bounded-error
communication complexity Omega(d), where d is the approximate degree
of f.

To illustrate our technique, we give a new proof of Razborov's
breakthrough quantum lower bounds (2003) for all functions of the
form f(x,y)=D(|x AND y|), where D:{0,1,...,n}->{0,1} is a given
predicate.  Our paper also establishes a large new class of functions
whose quantum communication complexity (regardless of prior
entanglement) is only polynomially smaller than their classical
complexity.

One of the ingredients of our proof is a certain equivalence of
approximation and orthogonality in Euclidean n-space, which follows
by linear-programming duality.  Another ingredient is a construction
of suitably structured matrices with low spectral norm, the
pattern matrices, which we realize using matrix analysis and
the Fourier transform over (Z_2)^n.

The method of this paper has recently enabled important progress
in multiparty communication complexity.