The Abel Lectures and Science Lecture
Location: Georg Sverdrups hus, Aud. 1, University of Oslo
23 May 2012 at 10:00 - 23 May 2012 at 15:15
Abel Laureate Endre Szemerédi will give his Abel Prize Lecture at the University of Oslo. The two other Abel Lectures will be given by László Lovász and Timothy Gowers. The Science Lecture will be delivered by Avi Wigderson.
Coffee and tea from 9:30 outside Auditorium 1.
10.00 Welome by Pro-Rector Inga Bostad, President of The Norwegian Academy of Science and Letters Nils Chr. Stenseth, and Chair of the Abel Committee Ragni Piene.
10.10 Professor Endre Szemerédi: "In Every Chaos There is an Order"
11.30 Professor László Lovász: The many facets of the Regularity Lemma"
12:30 Lunch (requires registration)
13.30 Professor Timothy Gowers: "The afterlife of Szemerédi's theorem"
14:30 Science Lecture: Avi Wigderson, "Randomness and Pseudorandomness"
15.15 Ending by Chair of the Abel Committee Ragni Piene
The aim of the Abel Lectures is to give a general audience a glimpse of the mathematics of the Abel Laureate and to convey to the general mathematician the importance and impact of his work. The Science Lecture is intended for the broader scientific community and aims to highlight connections between the work of the Abel Laureate and other sciences.
Avi Wigderson, Institute for Advanced Study
"Randomness and Pseudorandomness"
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 answers 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 Szemeredi's contributions to pseudorandomness.
The talk is aimed at a general audience, and no particular background will be assumed.