Lecture of Avi Wigderson
Location: Aula Franceschi, Via Sarfatti 25
Date: April 2nd, 2025
Time: 13:30
Registration link: https://www.unibocconi.it/en/events/randomness

Avi Wigderson is the Herbert H. Maass Professor at the School of Mathematics, Institute for Advanced Study, Princeton. He is one of the most prominent computer scientists, making important contributions to many research areas, including Algorithms and Optimization, Complexity Theory, Circuit Complexity, Quantum Computation, and Cryptography. For his scientific achievements, he was awarded Nevanlinna Prize (1994), Gödel Prize (2009), Knuth Prize (2019), Abel Prize (2021), and Turing Award (2023). We point out especially the Abel Prize and the Turing Award, since they are considered Nobel prizes of Mathematics and Computer Science respectively.
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 weekly random worlds. In the talk I’ll explain the main ideas and results of this theory.