NDLI: Three-Player Entangled XOR Games Are NP-Hard to Approximate

Content Provider	IEEE Xplore Digital Library
Author	Vidick, T.
Copyright Year	2013
Description	Author affiliation: Comput. Sci. & Artificial Intell. Lab., Massachusetts Inst. of Technol., Cambridge, MA, USA (Vidick, T.)
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 Há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.
Starting Page	766
Ending Page	775
File Size	246703
Page Count	10
File Format	PDF
ISBN	9780769551357
ISSN	02725428
DOI	10.1109/FOCS.2013.87
Language	English
Publisher	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Publisher Date	2013-10-26
Publisher Place	USA
Access Restriction	Subscribed
Rights Holder	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Subject Keyword	Games Approximation methods Polynomials Frequency modulation Q measurement Quantum entanglement Bell inequalities PCP theorem entangled games XOR games
Content Type	Text
Resource Type	Article

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

Three-Player Entangled XOR Games are NP-Hard to Approximate

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

Entangled Games are Hard to Approximate

Quantum XOR Games

Entangled Games Are Hard to Approximate

Three-player entangled XOR games . . . (2013)

Compression of quantum multi-prover interactive proofs

Two-player entangled games are NP-hard

A Parallel Repetition Theorem for Entangled Two-Player One-Round Games under Product Distributions

Three-Player Entangled XOR Games Are NP-Hard to Approximate

Similar Documents

Three-Player Entangled XOR Games are NP-Hard to Approximate

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

Entangled Games are Hard to Approximate

Quantum XOR Games

Entangled Games Are Hard to Approximate

Three-player entangled XOR games . . . (2013)

Compression of quantum multi-prover interactive proofs

Two-player entangled games are NP-hard

A Parallel Repetition Theorem for Entangled Two-Player One-Round Games under Product Distributions

Three-Player Entangled XOR Games Are NP-Hard to Approximate