  We study a model of communication complexity that encompasses many
well-studied problems, including classical and quantum communication
complexity, the complexity of simulating distributions arising from bipartite
measurements of shared quantum states, and XOR games. In this model, Alice gets
an input x, Bob gets an input y, and their goal is to each produce an output
a,b distributed according to some pre-specified joint distribution p(a,b|x,y).
  We introduce a new technique based on affine combinations of lower-complexity
distributions. Specifically, we introduce two complexity measures, one which
gives lower bounds on classical communication, and one for quantum
communication. These measures can be expressed as convex optimization problems.
We show that the dual formulations have a striking interpretation, since they
coincide with maximum violations of Bell and Tsirelson inequalities. The dual
expressions are closely related to the winning probability of XOR games. These
lower bounds subsume many known communication complexity lower bound methods,
most notably the recent lower bounds of Linial and Shraibman for the special
case of Boolean functions.
  We show that the gap between the quantum and classical lower bounds is at
most linear in the size of the support of the distribution, and does not depend
on the size of the inputs. This translates into a bound on the gap between
maximal Bell and Tsirelson inequality violations, which was previously known
only for the case of distributions with Boolean outcomes and uniform marginals.
  Finally, we give an exponential upper bound on quantum and classical
communication complexity in the simultaneous messages model, for any
non-signaling distribution. One consequence is a simple proof that any quantum
distribution can be approximated with a constant number of bits of
communication.
