A Seminar on
About the seminar
Randomness extractors are algorithms that "extract" randomness from imperfect random sources. The, perhaps, ideal notion of a randomness extractor does not exist, and so several types of extractors are being studied in the literature, including seeded extractors, two-source extractors, non-malleable extractors, and extractors for structured sources.
Randomness extractors have found many applications to theoretical computer science, combinatorics, coding theory, and cryptography to name a few. The study of extractors have led to the resolution of seemingly unrelated fundamental problems such as Kakeya sets over finite fields and the construction of Ramsey graphs. Thus, the construction of randomness extractors is a highly-motivated, fundamental problem that has attracted significant attention in the past few decades. Constructions of randomness extractors typically involve combinatorial as well as algebraic techniques.
In this seminar we will cover the, more or less, state-of-the art constructions of seeded extractors and quite modern (but not the best known) constructions of two extractors and non-malleable extractors. On the way, we will cover constructions of Ramsey graphs, and multi-source extractors.
This is a challenging graduate level seminar that can put the attentive student at a position in which she or he will be able to conduct research in the field. Each student is expected to present one paper from the list below. The papers will be presented in the order in which they appear. Most papers in the list cannot be fully covered within two hours. The student is therefore expected to understand the paper in full (except for a few sections the lecturer will exclude in some cases) and carefully choose what to present in detail and what to cover at a high-level.
There is no specific prerequisite other than what is taught at an undergraduate computer science (or math) degree, and indeed most of the constructions, although highly sophisticated, are elementary. However, in lecture 4 we will use basic facts from Fourier analysis of finite abelian groups.
List of papers
Part 0 - Introduction
Lecture 1. An introduction to randomness extractors by the lecturer.
Part 1 - Seeded extractors
Lecture 2. Kakeya sets, new mergers and old extractors by Dvir and Wigderson
Lecture 3. Unbalanced expanders and randomness extractors from Parvaresh–Vardy codes by Guruswami, Umans, and Vadhan
Part 2 - 3-Source extractors and 2-source dispersers
Lecture 4. An exposition of Bourgain’s 2-source extractor by Rao
Lecture 5. Extracting randomness using few independent sources by Barak, Impagliazzo and Wigderson
Lecture 7. Three-source extractors for polylogarithmic min-entropy by Li
Lecture 8. Two-source dispersers for polylogarithmic entropy and improved Ramsey graphs by Cohen
Part 3 - Non-malleable extractors and 2-source extractors
Lecture 9. Non-malleable extractors with short seeds and applications to privacy amplification by Cohen, Raz and Segev
Lecture 10. Local correlation breakers and applications to three-source extractors and mergers by Cohen
Lecture 11. Non-malleable extractors and codes, with their many tampered extensions by Chattopadhyay, Goyal, and Li
Lecture 12. Explicit two-source extractors and resilient functions by Chattopadhyay and Zuckerman
Lecture 13. An efficient reduction from two-source to non-malleable extractors: achieving near-logarithmic min-entropy by Ben-Aroya, Doron and Ta-Shma
Of course, there are many important papers that we cannot cover due to lack of time. This include some classical papers such as this, this, this, that and that, and newer results that continue where the seminar ended, including this, this, this, this, this and that.
Video talks on randomness extractors
A survey talk on extractors by Wigderson
A four parts introductory talk by Zuckerman on extractors and expanders.
A talk by Chattopadhyay on his construction of 2-source extractors with Zuckerman
A talk by Cohen about correlation breakers and independence preserving mergers
A talk on efficient reduction from non-malleable to 2-source extractors by Ta-Shma