IC Colloquium: The Value of Errors in Proofs
By: Avi Wigderson - School of Mathematics at the Institute for Advanced Study - Princeton University
Video of his talk
Abstract
A few months 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 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.
The talk does not require special mathematical background.
Bio
Avi Wigderson is a Professor in the School of Mathematics at the Institute for Advanced Study since 1999, where he leads the Institute's Computer Science and Discrete Math Program. He received his PhD in computer science in 1983 from Princeton University. During 1986-2001 he has held a permanent position at the Hebrew University Computer Science Institute, where he was the chair from 1992-95. Avi has held visiting positions at the University of California, Berkeley, IBM Research, the Mathematical Sciences Research Institute, Princeton University and the Institute for Advanced Study. His honors include being a two-time invited speaker at the International Congress of Mathematicians, where he was also presented in 1994 with the Nevanlinna Prize for outstanding contributions in mathematical aspects of information sciences. Avi gave the AMS Gibbs Lectures and received the AMS Conant Prize for mathematical exposition in 2008. He was the recipient of the 2009 Gödel Prize, which recognizes outstanding papers in theoretical computer science. In 2011 Avi was elected to the American Academy of Arts and Sciences, and in 2013 he was elected to the National Academy of Sciences.
More information
Video of his talk
Abstract
A few months 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 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.
The talk does not require special mathematical background.
Bio
Avi Wigderson is a Professor in the School of Mathematics at the Institute for Advanced Study since 1999, where he leads the Institute's Computer Science and Discrete Math Program. He received his PhD in computer science in 1983 from Princeton University. During 1986-2001 he has held a permanent position at the Hebrew University Computer Science Institute, where he was the chair from 1992-95. Avi has held visiting positions at the University of California, Berkeley, IBM Research, the Mathematical Sciences Research Institute, Princeton University and the Institute for Advanced Study. His honors include being a two-time invited speaker at the International Congress of Mathematicians, where he was also presented in 1994 with the Nevanlinna Prize for outstanding contributions in mathematical aspects of information sciences. Avi gave the AMS Gibbs Lectures and received the AMS Conant Prize for mathematical exposition in 2008. He was the recipient of the 2009 Gödel Prize, which recognizes outstanding papers in theoretical computer science. In 2011 Avi was elected to the American Academy of Arts and Sciences, and in 2013 he was elected to the National Academy of Sciences.
More information
Practical information
- General public
- Free
- This event is internal
Contact
- Host: Emmanuel Abbé and Michael Kapralov