top of page

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. Randomness-extractors 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 multi-source extractors. More intrinsic primitives such as mergers, condensers, non-malleable 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 randomness-extractors theory​

    • The Dvir-Wigderson curve-merger and the Kakeya set problem

    • The Guruswami-Umans-Vadhan lossless condenser

    • Two constructions of almost-optimal seeded extractors

    • Alternating extraction, the flip-flop primitive, and correlation breakers

    • Non-malleable extractors

  • Multi-source extractors​

    • Li's lightest-bin condenser​

    • Three-source extractors for polylogarithmic entropy

    • Two-source extractors based on extractors for non-oblivious bit-fixing 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 pseudo-randomness 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.

bottom of page