Randomness

Avi Wigderson, Institute for Advanced Study
Host: Xin Li

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 three 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. In particular we will discuss the basic notion(s) of “pseudo-randomness”, which turns out to capture fundamental problems in both Math and CS, and underlies a rapidly growing interaction area between them.

Speaker Biography

Avi Wigderson is Professor of Mathematics at the Institute for Advanced Study (Princeton), where he leads the Institute’s Computer Science and Discrete Math Program. He received his Ph.D. in computer science in 1983 from Princeton University. During 1986-2001 he held a permanent position at the Hebrew University Computer Science Institute and served as chair from 1992-95. Wigderson has held visiting positions at UC Berkeley, IBM Research, the Mathematical Sciences Research Institute, and the Institute for Advanced Study. He was an invited speaker at the International Congress of Mathematicians on two occasions, and was awarded the Nevanlinna Prize for outstanding contributions in mathematical aspects of information sciences in 1994. He gave the AMS Gibbs Lectures and received the AMS Conant Prize for mathematical exposition in 2008, and received the Gödel Prize, which recognizes outstanding papers in theoretical computer science, in 2009. Wigderson was elected to the American Academy of Arts and Sciences in 2011, and to the National Academy of Sciences in 2013.

Avi Wigderson works in the Theory of Computation, a field which studies the mathematical foundations of computer science. He is interested in the broad aspects of this exciting and rapidly developing field, including algorithms, Boolean and arithmetic circuit complexity, communication and proof complexity, cryptography, randomness, as well as the interactions of the field with other sciences including mathematics, physics, biology and economics.