The Della Pietra Lecture Series is pleased to present a series of lectures by Avi Wigderson, Institute for Advanced Study, Princeton
All talks will be streamed live at scgp.stonybrook.edu/live
Common Title and Abstract
“The Theory of Computation”
Speaker: Avi Wigderson, Institute for Advanced Study, Princeton
In this series of three (independent) lectures, I will explain different aspects of the theory of computation. In particular, we will discuss 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.
General Public Lecture
Wednesday November 12
Lecture at 4:00pm, Della Pietra Family Auditorium – 103
Wine and cheese reception, 5:00pm, Simons Center lobby
Following the lecture and reception, there will be a public concert by violinist Colin Carr and pianist Kyungwha Chu. More information can be found here: scgp.stonybrook.edu/archives/46958
Title: Randomness
Abstract: Is the universe inherently deterministic or probabilistic? Perhaps more importantly – can we tell the difference between the two? Humanity has pondered the meaning and utility of randomness for millennia. There is a remarkable variety of ways in which we utilize perfect coin tosses to our advantage: in statistics, cryptography, game theory, algorithms, gambling… Indeed, randomness seems indispensable!
Which of these applications survive if the universe had no randomness in it at all? Which of them survive if only poor-quality randomness is available, e.g. that arises from “unpredictable” phenomena like the weather or the stock market?
A computational theory of randomness, developed in the past four decades, reveals (perhaps counter-intuitively) that very little is lost in such deterministic or weakly random worlds. In the talk I’ll explain the main ideas and results of this theory.
This talk is designed for a general audience.
Special Talk for High School and Undergraduate Students
Thursday November 13 at 11:00am in Della Pietra Family Auditorium – 103
Title: What is computation?
Abstract: In this introductory talk, I will explain some of the main ideas underlying the computer revolution, electronic commerce, artificial intelligence and role of computation in understanding nature.
This talk is designed for high-school students, and will leave plenty of time for questions and discussion with the audience.
Technical Talk for Faculty and Advanced Graduate Students
Thursday November 13 at 2:00pm in SCGP room 102
Title: The Value of Errors in Proofs
(a 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 several long-standing problems in these areas.
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 mathematical background.
Avi Wigderson is the Herbert H. Maass Professor in the School of Mathematics at the Institute for Advanced Study (IAS). He earned his B.Sc. in Computer Science from the Technion in 1980, followed by a Ph.D. in Computer Science from Princeton University in 1983. After completing postdoctoral positions at UC Berkeley, IBM Research, and the Mathematical Sciences Research Institute (MSRI), he joined the Computer Science Department at the Hebrew University in 1986. In 1999, Wigderson became a faculty member at IAS, where he also founded the Computer Science and Discrete Mathematics program. His research spans a wide range of 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, mathematics, and other scientific fields. Wigderson’s influential work has earned him numerous honors, including the 2021 Abel Prize (shared with László Lovász) and the 2023 ACM A.M. Turing Award, recognizing both his foundational contributions to the theory of computation and his decades of intellectual leadership in the field.