License: Creative Commons Attribution 3.0 Unported license (CC-BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.CCC.2018.20
URN: urn:nbn:de:0030-drops-88696
Go to the corresponding LIPIcs Volume Portal

Natarajan, Anand ; Vidick, Thomas

Two-Player Entangled Games are NP-Hard

LIPIcs-CCC-2018-20.pdf (0.5 MB)


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 subseteq 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.

BibTeX - Entry

  author =	{Anand Natarajan and Thomas Vidick},
  title =	{{Two-Player Entangled Games are NP-Hard}},
  booktitle =	{33rd Computational Complexity Conference (CCC 2018)},
  pages =	{20:1--20:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-069-9},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{102},
  editor =	{Rocco A. Servedio},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{},
  URN =		{urn:nbn:de:0030-drops-88696},
  doi =		{10.4230/LIPIcs.CCC.2018.20},
  annote =	{Keywords: low-degree testing, entangled nonlocal games, multi-prover interactive proof systems}

Keywords: low-degree testing, entangled nonlocal games, multi-prover interactive proof systems
Collection: 33rd Computational Complexity Conference (CCC 2018)
Issue Date: 2018
Date of publication: 04.06.2018

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI