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.

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 6. Extractors for a constant number of independent sources with polylogarithmic min-entropy by Li

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

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, thisthis, that and that, and newer results that continue where the seminar ended, including 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