The communication complexity of non-signaling distributions

Understand

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.