Lunch will be served at 11:45 AM.
A few years ago, a group of theoretical computer scientists posted a paper on the Arxiv with the strange-looking title "MIP* = RE", surprising and impacting not only complexity theory but also some areas of math and physics. Specifically, it resolved, in the negative, the "Connes' embedding conjecture" in the area of von-Neumann algebras, and the "Tsirelson problem" in quantum information theory. It further connects Turing's seminal 1936 paper which defined algorithms, to Einstein's 1935 paper with Podolsky and Rosen which challenged quantum mechanics. You can find the paper here: https://arxiv.org/abs/2001.04383
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 (of 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.
Avi Wigderson is the Herbert H. Maas Professor in the School of Mathematics at the Institute for Advanced Study in Princeton, New Jersey, where he has been teaching since 1999. He also served in the Computer Science Institute at the Hebrew University in Jerusalem from 1986-2003. He earned his Ph.D. in Computer Science from Princeton University in 1983. His research interests include the Computational Complexity Theory, Algorithms and Optimization, Randomness and Cryptography, Parallel and Distributed Computation, Combinatorics and Graph Theory, and Connections of CS Theory with Math and Science. Avis was the 2023 winner of the A.M. Turing Award from the Association for Computing Machinery (ACM).
Department of Computer Science