Paper Info
Title
Two-player entangled games are NP-hard.
Abstract
We show that it is NP-hard to approximate, to within an additive constant, the maximum success probability of players sharing quantum entanglement in a two-player game with classical questions of logarithmic length and classical answers of constant length. As a corollary, the inclusion NEXP MIP , first shown by Ito and Vidick (FOCS'12) with three provers, holds with two provers only. The proof is based on a simpler, improved analysis of the low-degree test of Raz and Safra (STOC'97) against two entangled provers.
Year
DOI
Venue
2018
10.4230/LIPIcs.CCC.2018.20
Leibniz International Proceedings in Informatics
Keywords
DocType
Volume
low-degree testing,entangled nonlocal games,multi-prover interactive proof systems
Conference
102
ISSN
Citations 
PageRank 
1868-8969
1
0.36
References 
Authors
5
2
Name
Order
Citations
PageRank
Anand Natarajan1165.09
Thomas Vidick237731.69