Spring 2020

MIP* = RE Part 2: PCPs and Introspection

Wednesday, Apr. 1, 2020 2:15 pm3:15 pm PDT

Add to Calendar


John Wright (Caltech)

Continuing in the line of MIP* = RE talks, I will discuss two of the tools involved in the result, introspection and PCP composition, which are used to compress large MIP* protocols into small MIP* protocols. I will introduce these tools in the context of prior work with Anand Natarajan showing that MIP* contains NEEXP.

Joint work with Zhengfeng Ji, Anand Natarajan, Thomas Vidick, and Henry Yuen