NEEXP in MIP*

Understand

We study multiprover interactive proof systems.

• The power of classical multiprover interactive proof systems, in which the provers do not share entanglement, was characterized in a famous work by Babai, Fortnow, and Lund (Computational Complexity 1991), whose main result was the equality MIP = NEXP.
• The power of quantum multiprover interactive proof systems, in which the provers are allowed to share entanglement, has proven to be much more difficult to characterize.
• The best known lower-bound on MIP* is NEXP, due to Ito and Vidick (FOCS 2012).