Anand Natarajan

Anand Natarajan435

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
Sep 07 2017 17:44 UTC
Sep 07 2017 17:44 UTC
Sep 01 2017 15:20 UTC
Aug 31 2017 15:09 UTC
Aug 31 2017 15:09 UTC
Aug 09 2017 14:26 UTC
Anand Natarajan scited A fermionic de Finetti theorem
Aug 08 2017 22:12 UTC
Jul 26 2017 20:43 UTC
Jul 26 2017 20:43 UTC
Anand Natarajan scited Dynamics for holographic codes
Jun 16 2017 12:49 UTC
Jun 09 2017 02:36 UTC
Jun 08 2017 19:53 UTC