Grothendieck Inequalities, XOR Games, and Communication Complexity

An XOR game is a very simple model of evaluating a distributed function f(x,y) . With probability p(x,y) a Verifier sends questions x, y to Alice and Bob, respectively. Without communicating, Alice and Bob then output a, b in {-1,+1} in the hope that ab=f(x,y) . The bias of an XOR game is the probability under p that Alice and Bob are correct minus the probability they are incorrect. One can also study XOR games where the players Alice and Bob share entanglement. Grothendieck's famous inequality implies that the bias with entanglement can only be a constant factor larger than the bias without entanglement.

We consider XOR games in the multiparty setting. Here the situation becomes more interesting as the gap between the bias with and without entanglement can greatly depend on the particular state that is shared: Perez-Garcia et al. showed the existence of states which allow for unbounded gaps, while for so-called GHZ states the gap is constant. We enlarge the class of states for which we can prove bounded gaps in the bias by using multilinear generalizations of Grothendieck's inequality. We will also discuss the implications of these results for showing lower bounds on multiparty communication complexity with entanglement.

Joint work with Jop Briet, Harry Buhrman, and Thomas Vidick.