Avi Wigderson 7 September 2021

Title: The Value of Errors in Proofs – a fascinating journey from Turing’s seminal 1936 R ≠ RE to the 2020 breakthrough of MIP* = RE

As it happens, both acronyms MIP* and RE represent proof systems, of a very different nature. To explain them, we’ll take a meandering journey through the classical and modern definitions of proof. I hope to explain how the methodology of computational complexity theory, especially modeling and classification (both problems and proofs) by algorithmic efficiency, naturally leads to the generation of new such notions and results (and more acronyms, like NP). A special focus will be on notions of proof which allow interaction, randomness, and errors, and their surprising power and magical properties.

The talk does not assume any special background.