Theory Lunch Seminar

Wednesday, September 18, 2019 - 12:00pm to 1:00pm

Location:

ASA Conference Room 6115 Gates Hillman Centers

Speaker:

JOHN WRIGHT, Postdoctoral Researcher http://www.mit.edu/~jswright/

NEEXP in MIP*

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.

This is joint work with Anand Natarajan.

CMU Youtube Theory channel

Event Website:

http://www.cs.cmu.edu/~theorylunch/abstractsHTML/20190918.html

For More Information, Contact:

Keywords:

Seminar Series