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 counterintuitively) 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. No special background will be assumed.
Bio:
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.