Some interactions between mathematics and the theory of computation
Speaker: Avi Wigdserson, Institute for Advanced Study, Princeton
In this series of three (independent) lectures, if will explain three different research areas involving broad collaborations between mathematicians and computer scientists, which reveal new connections and lead to many beautiful results and important consequences. These three lectures are independent of each other, and do not assume any specific mathematical knowledge.
Lecture 1, February 4, 4:10-5 pm, Banatao Auditorium, Sutardja Dai Hall
A survey on expander graphs, and their constructions and applications
Abstract: Expander graphs are among the most useful objects in computer science and mathematics. They have found applications in numerous areas of both. I will review their definition, and explain some of the many applications. I will also discuss some of the different ways of constructing them, and ask some of my favorite open problems regarding them.
This talk requires no special background.
Lecture 2, February 5, 4:10-5 pm, Banatao Auditorium, Sutardja Dai Hall
The Value of Errors in Proofs – the fascinating journey from Turing’s 1936 R != RE to the 2020 breakthrough of MIP* = RE
Abstract: In the year 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: 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 (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.
This talk requires no special background.
Lecture 3, February 6, 4:10-5 pm, 60 Evans Hall (part of Colloquium series)
Optimization, Complexity and Math (or, can we prove P!=NP by gradient descent?)
Abstract: This talk aims to summarize a project I was involved in during the past decade, with the hope of explaining our most complete understanding so far, as well as challenges and open problems. It all started with a basic computational complexity problem involving intractability and pseudorandomness: deciding if a given matrix of linear forms is invertible. A new algorithm for a related problem, and its analysis, revealed numerous connections to different areas of math, CS and physics. A partial list includes invariant theory, analysis, optimization, geometry, quantum information and more. In this lecture I will try to relate some aspects of this meandering story and illustrate some of these diverse connections.
No special background is assumed. Based on joint works with Zeyuan Allen-Zhu, Peter Burgisser, Cole Franks, Ankit Garg, Leonid Gurvits, Pavel Hrubes, Yuanzhi Li, Visu Makam, Rafael Oliveira and Michael Walter.
Avi Wigderson is the Herbert H. Maass Professor in School of Mathematics at the Institute for Advanced Study. He received his B.Sc. in Computer Science from Technion in 1980, and his Ph.D. in Computer Science from Princeton University in 1983. In 1999, Avi joined IAS as faculty in the School of Math and founded the Computer Science and Discrete Mathematics program. His research interests are in 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. Avi has received many awards, including the 2021 Abel Prize (along with László Lovász) and most recently the 2023 ACM A.M. Turing Award for foundational contributions to the theory of computation, and for his decades of intellectual leadership in theoretical computer science.