TR07-100 Authors: Alexander A. Sherstov

Publication: 13th October 2007 15:32

Downloads: 1600

Keywords:

In a breakthrough result, Razborov (2003) gave optimal

lower bounds on the communication complexity of every function f

of the form f(x,y)=D(|x AND y|) for some D:{0,1,...,n}->{0,1}, in

the bounded-error quantum model with and without prior entanglement.

This was proved by the _multidimensional_ discrepancy method. We

give an entirely different proof of Razborov's result, using the

original, _one-dimensional_ discrepancy method. This refutes the

commonly held intuition (Razborov 2003) that the original discrepancy

method fails for functions such as DISJOINTNESS.

More importantly, our communication lower bounds hold for

a much broader class of functions for which no methods were available.

Namely, fix an arbitrary function f:{0,1}^{n/2} ->{0,1} and let A

be the Boolean matrix whose rows are each an application of f to

some subset of the variables x_1, NOT x_1, ..., x_n, NOT x_n. We

prove that the communication complexity of A in the bounded-error

quantum model with and without entanglement is \Omega(d), where d

is the (1/3)-approximate degree of f. From this result, Razborov's

lower bounds follow easily.

Our proof technique is novel and has two ingredients. The

first is a certain equivalence of approximation and orthogonality

in Euclidean n-space, which we establish using linear-programming

duality. The second is a new construction of suitably structured

matrices with low spectral norm, which we realize using matrix

analysis and the Fourier transform over (Z_2)^n.