Randomness extractors are algorithms that convert imperfect random sources into uniform random strings. These objects bridge "randomness from nature", which we have less confidence in, with uniform randomness that we would like to use in applications. While an "ideal randomness extractor" does not exist, there are fruitful results on randomness extractors in the literature for different restricted settings. These extractor constructions have found many applications in theoretical computer science, cryptography and combinatorics. In this course, we will cover several classic results on the construction of randomness extractors and some important applications of randomness extractors. A big part of this course will focus on modern constructions of extractors for two independent sources.
Time and Location:
Mon, Wed 3:00pm~4:20pm, CSE building (EBU3B), Room 3109
Grading
Grades will be based on a homework and a final project.
Notes and Homeworks
Lecture Note (Updated on May 6, until Lecture 7: Raz's Extractors)
Homework 1 (Due May 26, 11:59pm. Updated on May 9: Corrected some typos. May 14 Update: Ignore Problem 3, the intended approach was wrong. Deadline extended due to this update.)
HW1 Source Code
Final Project
The final project is due before the start of Fall 2025. It can be any report about this course, including a review of some interesting papers, discussions about some open problems, etc. If you don't know what you are going to write about, below is a list of papers that I think are important but didn't have time to go through in the lectures. (Will keep updating this list.)
Trevisan's Extractor: a simple seeded extractor with really good parameters, which is constructed based on connection to pseudorandom generators. You might want to check some follow-up works such as this one.
Two-source Extractors with Asymptotically Optimal Entropy: the two-source extractor with state-of-the-art entropy requirement (O(log n)).
Recommended Readings
This list will be updated throughout the course.
Pseudorandomness by Salil Vadhan
This survey by Salil Vadhan covers many important concepts in pseudorandomness. Specifically, Chapter 6 is about seeded extractors, which would be our main focus in the first few weeks. Randomness extractors has connection with many other pseudorandom objects, but in this class we will only introduce those appear in our construction of extractors. So if you want to understand other pseudorandom objects in more details, this survey is an excellent reference.
Essential Coding Theory
If you want to learn more about error correcting code.