Anand Natarajan

Anand Natarajan435

Dec 07 2017 13:24 UTC
Dec 06 2017 04:24 UTC
Nov 30 2017 12:52 UTC
Nov 30 2017 12:52 UTC
Nov 29 2017 13:13 UTC
Nov 28 2017 15:28 UTC
Nov 21 2017 18:02 UTC
Nov 20 2017 08:13 UTC
Nov 16 2017 08:35 UTC
Nov 02 2017 08:08 UTC
Oct 17 2017 09:02 UTC
Oct 10 2017 08:56 UTC
Oct 10 2017 02:00 UTC
Anand Natarajan published Two-player entangled games are NP-hard
We show that 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 is NP-hard to approximate to within constant factors. As a corollary, the inclusion $\mathrm{NEXP}\subseteq\mathrm{MIP}^*$, first shown in [IV12] with three provers, holds with two provers only. The proof is based on a simpler, improved analysis of the low-degree test Raz and Safra (STOC'97) against two entangled provers.
Oct 09 2017 07:18 UTC
Sep 28 2017 09:04 UTC