Randomness Extractors Theory
What this course is about?
Generally speaking, a randomness extractor is an algorithm that produces truly random bits given a sample from one or more "weak" sources of randomness. Extractors are central objects in theoretical computer science that have found many applications in complexity theory, cryptography, data structures, and combinatorics, to name a few. Randomnessextractors theory is a vibrant research field that makes frequent use of coding theory, additive combinatorics, Fourier analysis, and more.
In this course, we will cover constructions of the main two types of extractors  seeded extractors and multisource extractors. More intrinsic primitives such as mergers, condensers, nonmalleable extractors, and correlation breakers will be presented as well. We will discuss some applications to privacy, data structures, and Ramsey theory, among others.
Syllabus

Seeded extractors

Introduction to randomnessextractors theory

The DvirWigderson curvemerger and the Kakeya set problem

The GuruswamiUmansVadhan lossless condenser

Two constructions of almostoptimal seeded extractors

Alternating extraction, the flipflop primitive, and correlation breakers

Nonmalleable extractors


Multisource extractors

Li's lightestbin condenser

Threesource extractors for polylogarithmic entropy

Twosource extractors based on extractors for nonoblivious bitfixing sources

Literature and useful links
This course is not based on any specific book but rather on recent papers, though there are some great sources out there that cover some of what we will talk about. Some of which are:

Salil Vadhan's monograph on pseudorandomness. Extractors are covered in Chapter 6.

Ronen Shaltiel's survey on randomness extractors.

A great video talk by Avi Wigderson on randomness extractors. A theorem you should prove to yourself  all of Avi's talks are great! You can start with very related talks on randomness and pseudorandomness and on expander graphs  part 1 and part 2.

A video talk by Xin Li on one of the central papers that generated the exciting recent developments in extractors theory.
Papers this course is based on: