Harald Bohr Lecture: Avi Wigderson

Title: Randomness

Speaker: Avi Wigderson (Herbert H. Maass Professor, 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 in life, and a very powerful tool in algorithms!

Which (if any) of these applications of randomness  survive if the universe had no (accessible) randomness in it at all? Which (if any) 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 and their meaning. These include new notions of pseudo-randomness, and how they naturally arise in Math and CS.