University of Montréal
Title: The communication complexity of non-signalling distributions
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).
By introducing a simple new technique based on affine combinations of
lower-complexity distributions, we give the first general technique to
apply to all these settings, with elementary proofs and very intuitive
interpretations. Despite their apparent simplicity, these lower bounds
subsume many known communication complexity lower bound methods, most
notably the lower bounds of Linial and Shraibman for the special case
of Boolean functions.
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 of this is a simple proof
that any quantum distribution can be approximated with a constant
number of bits of communication.