May 24, 2024
Thematic Program on Asymptotic Geometric Analysis
July - December 2010

September 14-16, 2010
Fields Institute, Room 230

Distinguished Lecture Series
Avi Wigderson
Institute for Advanced Study, Princeton
Randomness, Pseudorandomness and Derandomization

Lecture 1: The power and weakeness of randomness (when you are short on time)
Lecture 2: Pseudoradomness in cryptography (and beyond)
Lecture 3: Expander graphs: a ubiquitous pseudorandom structure

Man has grappled with the notion of randomness for centuries. In the past few decades, the computational viewpoint begun to shed new light on this fundamental notion. This series of lectures will explore, exemplify and explain some aspects of this new understanding, focusing on the following themes.

The computational power of randomness: The use of randomness in algorithms and cryptography has greatly enriched the collection of tasks which can be performed efficiently. On the other hand, the question to which extent is this power of randomness real has lead to precise definitions of pseudorandomness and derandomization, and to their fundamental relation to computational difficulty.

Explicit construction of pseudorandom objects: Parallel strands of research in computer science and mathematics pursued the understanding of objects, like expander graphs and randomness extractors, which have strong pseudorandom properties. Such objects have numerous applications in both areas, which called for their efficient, explicit constructions.

These topics are today a focus of great (often joint) research activity of mathematicians and computer scientists, and we'll survey both main accomplishments as well as main outstanding challenges.

The lectures are aimed at a general mathematics and computer science audience, and requires no special knowledge. We will attempt to make the lectures relatively independent of each other, so as to accommodate
people who can attend only a subset.

Speakers in the Distinguished Lecture Series (DLS) have made outstanding contributions to their field of mathematics. The DLS consists of a series of three one-hour lectures.
Index of Fields Distinguished and Coxeter Lectures

Thematic Year Home page