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.