Number Theory Web Seminar: Avi Wigderson (Institute for Advanced Study)

Randomness

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.

For further information about the seminar, please visit this webpage.

Veranstaltung übernehmen als iCal