A Seminar on
Randomness Extractors
Fall 2022/23
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.
Technicalities
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.
When & where
Monday 9:10-11:00 at Schreiber 007.
List of papers
Part 0 - Introduction
Lecture 1. An introduction to randomness extractors (given by Gil). Slides.
Lecture 2. Kakeya sets, new mergers and old extractors by Dvir and Wigderson (given by Gil).
Part 1 - Seeded extractors
Lecture 3. Applications of extractors to samplers, space-bounded derandomization, and privacy amplification (given by Gil).
Lecture 4. Basic constructions of extractors from Vadhan's survey (given by Itamar).
Lecture 6 (yes, 6). Unbalanced expanders from multiplicity codes by Kalev and Ta-Shma (given by Amnon)
Part 2 - 3-Source extractors and 2-source dispersers
Lecture 5 (yes, 5). Two-source dispersers for polylogarithmic entropy and improved Ramsey graphs by Cohen (given by Gil)
Lecture 7. An exposition of Bourgain’s 2-source extractor by Rao (given by Maya).
Lecture 8. Extracting randomness using few independent sources by Barak, Impagliazzo and Wigderson (given by Tal).
Lecture 10 (yes, 10). Extractors for a constant number of independent sources with polylogarithmic min-entropy by Li (given by Roy).
Part 3 - Non-malleable extractors and 2-source extractors
Lecture 9 (yes, 9). Non-malleable extractors with short seeds and applications to privacy amplification by Cohen, Raz and Segev (given by Gil)
Lecture 11. Local correlation breakers and applications to three-source extractors and mergers by Cohen (Given by Gil)
Lecture 12. Non-malleable extractors and codes, with their many tampered extensions by Chattopadhyay, Goyal, and Li (given by Omer Benami)
Lecture 13. Explicit two-source extractors and resilient functions by Chattopadhyay and Zuckerman (given by Tommy)
Other references
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, this, this, and that, and newer results that continue where the seminar will end, including this, this, this, this, this, this, this and that.
Good surveys, mostly on seeded extractors, include Chapter 6 in Vadhan's book and a survey by Shaltiel. For a survey on recent advances, see Chattopadhyay's survey.
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 two part talk (part 1, part 2) on Ramsey graphs construction by Cohen
A talk on efficient reduction from non-malleable to 2-source extractors by Ta-Shma