The Value of Errors in Proofs

Add to your list(s) Download to your calendar using vCal

• Avi Wigderson (IAS, Princeton)
• Monday 15 April 2024, 14:00-15:00
• Computer Laboratory, William Gates Building, LT1.

If you have a question about this talk, please contact Tom Gur.

Recently, 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 jurney 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 genaration 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.

This talk is part of the Algorithms and Complexity Seminar series.

This talk is included in these lists:

• Algorithms and Complexity Seminar
• All Talks (aka the CURE list)
• Cambridge talks
• Computer Laboratory, William Gates Building, LT1
• Department of Computer Science and Technology talks and seminars
• Interested Talks
• School of Technology
• Trust & Technology Initiative - interesting events
• bld31
• ki287

Note that ex-directory lists are not shown.