TCS+ Talk (Live Stream)

  • Gates Hillman Centers
  • Traffic21 Classroom 6501
  • JOHN WRIGHT
  • Postdoctoral Researcher
  • Center for Theoretical Physics
  • Massachusetts Institute of Technology
Talks

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 NEXP of 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.

TCS+, a series of online seminars in theoretical computer science, will solve all your worries. The seminars are run using Google Hangouts. The speaker and slides are broadcast live, as well as recorded and made available online. Anyone can watch the live broadcast, or even join the live audience and participate. The goal is to make engaging talks accessible to the widest possible audience, thereby ensuring a carbon-free dissemination of ideas across the globe.

Stream

Keywords: