Abstract
We bound separations between the entangled and classical values for several classes of nonlocal tplayer games. Our motivating question is whether there is a family of tplayer XOR games for which the entangled bias is 1 but for which the classical bias goes down to 0, for fixed t. Answering this question would have important consequences in the study of multiparty communication complexity, as a positive answer would imply an unbounded separation between randomized communication complexity with and without entanglement. Our contribution to answering the question is identifying several general classes of games for which the classical bias can not go to zero when the entangled bias stays above a constant threshold. This rules out the possibility of using these games to answer our motivating question. A previously studied set of XOR games, known not to give a positive answer to the question, are those for which there is a quantum strategy that attains value 1 using a socalled Schmidt state. We generalize this class to modm games and show that their classical value is always at least 1/m + (m1)/m t^{1t}. Secondly, for free XOR games, in which the input distribution is of product form, we show beta(G) >= beta^*(G)^{2^t} where beta(G) and beta^*(G) are the classical and entangled biases of the game respectively. We also introduce socalled line games, an example of which is a slight modification of the Magic Square game, and show that they can not give a positive answer to the question either. Finally we look at twoplayer unique games and show that if the entangled value is 1epsilon then the classical value is at least 1O(sqrt{epsilon log k}) where k is the number of outputs in the game. Our proofs use semidefiniteprogramming techniques, the Gowers inverse theorem and hypergraph norms.
BibTeX  Entry
@InProceedings{bannink_et_al:LIPIcs:2019:10251,
author = {Tom Bannink and Jop Bri{\"e}t and Harry Buhrman and Farrokh Labib and Troy Lee},
title = {{Bounding QuantumClassical Separations for Classes of Nonlocal Games}},
booktitle = {36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019)},
pages = {12:112:11},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959771009},
ISSN = {18688969},
year = {2019},
volume = {126},
editor = {Rolf Niedermeier and Christophe Paul},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2019/10251},
doi = {10.4230/LIPIcs.STACS.2019.12},
annote = {Keywords: Nonlocal games, communication complexity, bounded separations, semidefinite programming, pseudorandomness, Gowers norms}
}
Keywords: 

Nonlocal games, communication complexity, bounded separations, semidefinite programming, pseudorandomness, Gowers norms 
Collection: 

36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019) 
Issue Date: 

2019 
Date of publication: 

12.03.2019 