Turing Award Prof. Avi Wigderson at University of Rome Tor Vergata

Information
Speaker Prof. Avi Wigderson (School of Mathematics, Institute for Advanced Study, Princeton)
Title The Value of Errors in Proofs - the fascinating journey from Turing's 1936 R ≠ RE to the 2020 breakthrough of MIP* = RE
Room Aula Gismondi, Macroarea Scienze MM.FF.NN, Tor Vergata University of Rome
Date Thursday, October 31, 2024
Hour 3:00 PM

Abstract

In 2020, a group of theoretical computer scientists posted a paper on the Arxiv with the strange-looking title "MIP* = RE", impacting and surprising 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. You can find the paper here.

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, including ZK (Zero Knowledge proofs) and PCPs (Probababilistically Checkable Proofs). The talk will be non-technical, and requires no special background.

Schedule
14:45 Institutional Greetings
14:50 Introducing Prof. Wigderson
15:00 Prof. Wigderson's Talk: "The Value of Errors in Proofs"
16:30 Coffee Break
17:30 End of the Event

Professor
Avi Wigderson

Avi Wigderson

Avi Wigderson is the Herbert H. Maass Professor in the School of Mathematics at the Institute for Advanced Study in Princeton, New Jersey. He has been a leading figure in areas including computational complexity theory, algorithms and optimization, randomness and cryptography, parallel and distributed computation, combinatorics, and graph theory, as well as connections between theoretical computer science and mathematics and science.

Wigderson’s honors include the Abel Prize, the IMU Abacus Medal (previously known as the Nevanlinna Prize), the Donald E. Knuth Prize, the Edsger W. Dijkstra Prize in Distributed Computing, and the Gödel Prize. He is an ACM Fellow and a member of the U.S. National Academy of Sciences and the American Academy of Arts and Sciences.

ACM has named Avi Wigderson as recipient of the 2023 ACM A.M. Turing Award for foundational contributions to the theory of computation, including reshaping our understanding of the role of randomness in computation, and for his decades of intellectual leadership in theoretical computer science. The ACM A.M. Turing Award, often referred to as the "Nobel Prize in Computing", carries a 1 million prize with financial support provided by Google, Inc. The award is named for Alan M. Turing, the British mathematician who articulated the mathematical foundations of computing.

Prof. Wigderson is the only scientist to hold both the Abel Prize and the Turing Award.


For any question, please contact Andrea Clementi at clementi@mat.uniroma2.it.