Computer Science/Discrete Mathematics Seminar I

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.