Re: [theory students] [theory faculty] Theory lunch on Wednesday in 3310

[Shuchi Chawla <shuchi@xxxxxxxxxxx>]

FYI this talk is starting now. This result is getting a lot of attention, so everyone is highly encouraged to attend!

Shuchi

On Mon, Feb 24, 2020, 5:08 PM YIFENG TENG <yifengt@xxxxxxxxxxx> wrote:

Hi all,

We will haveÂtheoryÂlunchÂon Wednesday at noon in CS 3310. We are going to watch theÂTCS+ talk by Henry Yuen from U Toronto on "MIP*=RE." Bring yourÂlunch, and see you there!

Please sign up if you want to give a talk in the following spreadsheet.Âhttps://docs.google.com/spreadsheets/d/1Yz0iMLhoqUMSY_4aTcGYMDOyJXb5cDq8xB7cgjjzBy0/edit?usp=sharing

Below is the abstract of Wednesday's talk.Â

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.

Best,

Yifeng

-------------------------------------------------------------------------------
This message was sent to the mailing list for the theory faculty at the
Computer Sciences Department of the University of Wisconsin in Madison.