Speaker
Avi Wigderson
Herbert H. Maass Professor at the School of Mathematics,
Institute for Advanced Study, Princeton
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 weekly random worlds. In the talk I’ll explain the main ideas and results of this theory.
Avi Wigderson is the Herbert H. Maass Professor in the School of Mathematics at the Institute for Advanced Study in Princeton, New Jersey.
He has been a leading figure in 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 and mathematics and science.
Wigderson’s honors include the Abel Prize, the IMU Abacus Medal (previously known as the Nevanlinna Prize), the Donald E. Knuth Prize, the Edsger W. Dijkstra Prize in Distributed Computing, and the Gödel Prize. He is an ACM Fellow and a member of the U.S. National Academy of Sciences and the American Academy of Arts and Sciences.
ACM has named Avi Wigderson as recipient of the 2023 ACM A.M. Turing Award for foundational contributions to the theory of computation, including reshaping our understanding of the role of randomness in computation, and for his decades of intellectual leadership in theoretical computer science. The ACM A.M. Turing Award, often referred to as the "Nobel Prize in Computing", carries a 1 million prize with financial support provided by Google, Inc. The award is named for Alan M. Turing, the British mathematician who articulated the mathematical foundations of computing.
Prof. Wigderson is the only scientist to hold both the Abel Prize and the Turing Award.
