Avi Wigderson: Randomness (NTWS 106)

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 (accessible) randomness in it at all? Which of them survive if only poor quality randomness is available, e.g. that arises from somewhat "unpredictable" phenomena like the weather or the stock market?
A computational theory of randomness, developed in the past several 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, notions of pseudo-randomness, and connections to computational intractability.
It is interesting that Number Theory played an important role throughout this development. It supplied problems whose algorithmic solution make randomness seem powerful, problems for which randomness can be eliminated from such solutions, and problems where the power of randomness remains a major challenge for computational complexity theorists and mathematicians. I will use these problems (and others) to demonstrate aspects of this theory.
Link to slides: drive.google.c...
Number Theory Web Seminar: www.ntwebsemin...
Original air date:
Thursday, November 11, 2021 (8am PST, 11am EST, 4pm GMT, 5pm CET, 6pm Israel Standard Time, 9:30pm Indian Standard Time)
Friday, November 12, 2021 (12am CST, 3am AEDT, 5am NZDT)