A Caltech Library Service

Three-player entangled XOR games are NP-hard to approximate

Vidick, Thomas (2013) Three-player entangled XOR games are NP-hard to approximate. In: IEEE 54th Annual Symposium on Foundations of Computer Science (FOCS). IEEE , Piscataway, NJ, pp. 766-775. ISBN 978-0-7695-5135-7.

PDF - Submitted Version
See Usage Policy.


Use this Persistent URL to link to this item:


We show that for any ε > 0 the problem of finding a factor (2 - ε) approximation to the entangled value of a three-player XOR game is NP-hard. Equivalently, the problem of approximating the largest possible quantum violation of a tripartite Bell correlation inequality to within any multiplicative constant is NP-hard. These results are the first constant-factor hardness of approximation results for entangled games or quantum violations of Bell inequalities shown under the sole assumption that P≠NP. They can be thought of as an extension of Hástad's optimal hardness of approximation results for MAX-E3-LIN2 (JACM'01) to the entangled-player setting. The key technical component of our work is a soundness analysis of a point-vs-plane low-degree test against entangled players. This extends and simplifies the analysis of the multilinearity test by Ito and Vidick (FOCS'12). Our results demonstrate the possibility for efficient reductions between entangled-player games and our techniques may lead to further hardness of approximation results.

Item Type:Book Section
Related URLs:
URLURL TypeDescription DOIArticle ItemJournal Article Paper
Vidick, Thomas0000-0002-6405-365X
Additional Information:© 2013 IEEE. Supported by the National Science Foundation under Grant No. 0844626.
Funding AgencyGrant Number
Subject Keywords:PCP theorem; entangled games; XOR games; Bell inequalities
Record Number:CaltechAUTHORS:20140910-100149541
Persistent URL:
Official Citation:Vidick, T., "Three-Player Entangled XOR Games Are NP-Hard to Approximate," Foundations of Computer Science (FOCS), 2013 IEEE 54th Annual Symposium on , vol., no., pp.766,775, 26-29 Oct. 2013 doi: 10.1109/FOCS.2013.87 URL:
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:49529
Deposited By: Tony Diaz
Deposited On:10 Sep 2014 18:40
Last Modified:10 Nov 2021 18:45

Repository Staff Only: item control page