The communication complexity of non-signaling distributions

The communication complexity of non-signaling distributions

Abstract:

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). Our results apply to any non-signaling distribution, that is, those where Alice's marginal distribution does not depend on Bob's input, and vice versa. Our techniques apply to any communication problem that can be reduced to a non-signaling distribution, including non- Boolean functions, most relations, partial (promise) problems, and multipartite settings.
The proofs are surprisingly easy and give very intuitive interpretations of the recent lower bounds of Linial and Shraibman, which is shown to be a special case of our method, for Boolean functions. Our lower bounds can be expressed as linear programs (or SDPs for quantum communication), and the dual formulations have a striking interpretation, since they coincide with maximum violations of Bell and Tsirelson inequalities. The dual expressions are shown to be closely related to the winning probability of XOR games.