Avi Wigderson: Randomness and pseudorandomness @AbelPrize
Avi Wigderson: Randomness and pseudorandomness  @AbelPrize
Uploaded February 2020 | Updated November 2026, 2 hours ago
Abstract:
The talk is aimed at a general audience, and no particular background will be assumed.

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?

Pseudorandomness is the study, by mathematicians and computer scientists, of deterministic structures which share some properties of random ones. Understanding pseudorandom objects and constructing them efficiently leads to a surprisingly positive answer to the questions above, namely that much can be done with poor quality randomness, of even without any randomness at all. I plan to explain key aspects of this theory, and mention some of Endre Szemerédi's contributions to pseudorandomness.

This lecture was held at The University of Oslo, May 23, 2012 and was part of the Abel Prize Lectures in connection with the Abel Prize Week celebrations.

Program for the Abel Lectures 2012:
1. "In every chaos there is an order" by Abel Laureate Endre Szemerédi
2. "The many facets of the Regularity Lemma" by professor László Lovász
3. "The afterlife of Szemerédi's theorem" by professor Timothy Gowers
4. "Randomness and pseudorandomness" a science lecture by professor Avi Wigderson
Avi Wigderson: Randomness and pseudorandomnessMichael Hopkins: My best advice to young mathematicians (2022)László Lovász: The many facets of the Regularity LemmaThe Norwegian Prime Minister and the Minister of Education congratulates Michel Talagrand (2024)Interview with Hillel Furstenberg and Gregory Margulis - Abel Prize Laureates 2020Endre Szemerédi - The Abel Prize interview 2012The Abel Prize Interview: Michel Talagrand (2024) with Dundas & SkauJohn Christian Ottem: Advice to Young Mathematicians (2025)Gerd Faltings - Official Abel Prize laureate portrait 2026Hee Oh: A Eucledian travelers journey in a hyperbolic worldEveryone else understood. I didnt. | Hee Oh - Advice to young mathematicians - Abel Prize 2026Hillel Furstenberg: Why I went into mathematics (2022)
The Abel Prize |

Avi Wigderson: Randomness and pseudorandomness

SHARE TO X SHARE TO REDDIT SHARE TO FACEBOOK WALLPAPER