Caltech Logo

TCS+ Talk

Wednesday, June 12, 2019
10:00am to 11:00am
Add to Cal
Annenberg 322
NEEXP in MIP*
John Wright, Postdoctoral Associate, MIT,

Abstract: A long-standing puzzle in quantum complexity theory is to understand the power of the class MIP* of multiprover interactive proofs with shared entanglement. This question is closely related to the study of entanglement through non-local games, which dates back to the pioneering work of Bell. In this work we show that MIP* contains NEEXP (non-deterministic doubly-exponential time), exponentially improving the prior lower bound of NEXP due to Ito and Vidick. Our result shows that shared entanglement exponentially increases the power of these proof systems, as the class MIP of multiprover interactive proofs without shared entanglement is known to be equal to NEXP.

For more information, please contact Bonnie Leung by email at bjleung@caltech.edu.