The discrepancy method is a general technique to show lower bounds on
the communication two separated parties need to exchange in order to
compute some distributed function. Discrepancy was the first general
technique available to show lower bounds on quantum communication
complexity, and is still the easiest bound to use for many applications.

We show a product theorem for discrepancy, namely that the
discrepancy of the function f(x_1,y_1) XOR f(x_2, y_2) is equal to
the product of the discrepancies of f and g, up to a small
multiplicative constant. This answers an open question of Shaltiel
would had previously shown a weaker product theorem for discrepancy
under the uniform distribution.

Our result implies that if you show a lower bound of c on the quantum
communication complexity of a function f by the discrepancy method,
then the parity of two independent copies of f requires quantum
communication at least 2c. Our result also has interesting
connections to a recent product theorem of Cleve et al. for quantum
XOR games, which we will discuss.

This is joint work with Adi Shraibman and Robert Spalek.