This was part of Quantum Information for Mathematics, Economics, and Statistics

The proofs perspective on MIP* = RE

Henry Yuen, Columbia University

Wednesday, May 26, 2021



Abstract: The recently established equality of the complexity classes MIP* and RE has surprising consequences for complexity theory, mathematical physics, and functional analysis. In this talk I'll discuss this result from the point of view of proof systems, including how interactive proofs and probabilistically checkable proofs play a central role. I'll also discuss how MIP* = RE points to an interesting set of questions that can be categorized as "noncommutative property testing".