[Theory] TCS+ Talk - MIP="RE"

[Tushant Mittal]

Hi everyone,

We will be having a live screening tomorrow of the TCS+ Talk by Henry Yuen
on the breakthrough result, MIP*=RE. Everyone who is interested is welcome.

When: Wednesday, February 26 at 12:00 PM

Where: Crerar 346

Who: Henry Yuen

Title: MIP*=RE Abstract: MIP* denotes the class of problems that admit
interactive proofs with quantum entangled provers. It has been an
outstanding question to characterize the complexity of MIP*. Most notably,
there was no known computable upper bound on this class. We show that MIP*
is equal to the class RE, the set of recursively enumerable languages. In
particular, this shows that MIP* contains uncomputable problems. Through a
series of known connections, this also yields a negative answer to Connes’
Embedding Problem from the theory of operator algebras. In this talk, I
will explain the connection between Connes’ Embedding Problem, quantum
information theory, and complexity theory. I will then give an overview of
our approach, which involves reducing the Halting Problem to the problem of
approximating the entangled value of nonlocal games. Joint work with
Zhengfeng Ji, Anand Natarajan, Thomas Vidick, and John Wright.

Regards,
Tushant
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mailman.cs.uchicago.edu/pipermail/theory/attachments/20200225/cc03a930/attachment.html>