Till innehåll på sidan

Avi Wigderson: Randomness

Tid: Fr 2017-05-19 kl 13.15 - 14.15

Plats: D1, Lindstedtsvägen 17, D-huset, KTH

Medverkande: Avi Wigderson, Institute for Advanced Study, Princeton

Exportera till kalender

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
discuss the main ideas and results of this theory, give a mathematical
definition of pseudorandomness, and explain how both the Riemann
Hypothesis and the P vs. NP question (among others) naturally fit in
this framework.

The talk is aimed at a general scientific audience.