Marc Kaplan
University of MontrĂ©al
Title: The communication complexity of nonsignalling distributions
We study a model of communication complexity that encompasses many
wellstudied 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
prespecified joint distribution p(a,bx,y).
By introducing a simple new technique based on affine combinations of
lowercomplexity 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
nonsignaling distribution. One consequence of this is a simple proof
that any quantum distribution can be approximated with a constant
number of bits of communication.
