CaltechAUTHORS
  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. https://resolver.caltech.edu/CaltechAUTHORS:20140910-100149541

[img]
Preview
PDF - Submitted Version
See Usage Policy.

479kB

Use this Persistent URL to link to this item: https://resolver.caltech.edu/CaltechAUTHORS:20140910-100149541

Abstract

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
http://dx.doi.org/10.1109/FOCS.2013.87 DOIArticle
http://resolver.caltech.edu/CaltechAUTHORS:20161103-145636436Related ItemJournal Article
http://arxiv.org/abs/1302.1242arXivDiscussion Paper
ORCID:
AuthorORCID
Vidick, Thomas0000-0002-6405-365X
Additional Information:© 2013 IEEE. Supported by the National Science Foundation under Grant No. 0844626.
Funders:
Funding AgencyGrant Number
NSFCCF-0844626
Subject Keywords:PCP theorem; entangled games; XOR games; Bell inequalities
DOI:10.1109/FOCS.2013.87
Record Number:CaltechAUTHORS:20140910-100149541
Persistent URL:https://resolver.caltech.edu/CaltechAUTHORS:20140910-100149541
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: http://ieeexplore.ieee.org/stamp/stamp.jsp?tp=&arnumber=6686213&isnumber=6686124
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:49529
Collection:CaltechAUTHORS
Deposited By: Tony Diaz
Deposited On:10 Sep 2014 18:40
Last Modified:10 Nov 2021 18:45

Repository Staff Only: item control page