STOC 2018 Theory Fest workshop on
Randomness Extractors: Constructions and Applications
Eshan Chattopadhyay, Xin Li and I organized a workshop entitled Randomness extractors: Constructions and Applications. This halfday workshop was held on June 29 2018 as part of the STOC 2018 Theory Fest. Below is the workshop schedule, slides of the talks, and links to related papers.
Overview. The theory of randomness extractors is concerned with "extracting" truly uniform random bits from "weak" random sources. Randomness extractors are fundamental objects in the study of pseudorandomness, and have wide applications in computer science. Randomness extractors have been extensively studied for more than three decades. Yet, this field is still rapidly developing. Especially, in the last decade or so, there has been a burst of significant progress on several different models of randomness extractors that were considered hard to construct. This line of work has led to a rich set of new techniques and to the resolution of several long standing open problems.
This fast development of the theory makes the results hard to follow. The goal of this workshop is to survey recent advances in the field while emphasizing the new techniques developed, new connections established, and potential applications that may interest the theory community at large. Intriguing open problems will also be discussed.
Schedule
The workshop will be held on June 29th 8:4511:45.
Location: Bradbury/Rose, Omni Hotel, LA.
8:459:15
Randomness Extractors: An Introduction
David Zuckerman (UT Austin)
A randomness extractor is an efficient algorithm that extracts highquality randomness from a lowquality random source. We examine when such randomness extraction is possible, surveying seeded, seedless, and multisource extractors.
9:159:45
Mergers and Kakeya sets
Zeev Dvir (Princeton University)
A Kakeya sets is a set containing lines in all (or many) different directions (over a finite field). Lower bounds on the size of Kakeya sets stand at the basis of the current state of the art in seeded extractors. These bounds allow us to analyze a very simple family of "randomness mergers", which are important building blocks in extractor constructions. In this talk I will survey the known constructions and outline some open problems that still remain in this area and could potentially lead to better seeded extractors.
References

The analysis without multiplicities is given in the paper Kakeya Sets, New Mergers, and Old Extractors by Dvir and Wigderson. See also this earlier paper of Dvir and Shpilka. The more involved analysis with multiplicities is given here. I advise to take a look at Zeev's survey.

If you feel adventurous, see Amnon TaShma's thesis for the origin of mergers.
9:4510:15
Quantumproof extractors: definition, constructions, applications, and open questions
Thomas Vidick (California Institute of Technology)
This talk will provide an introduction to the problem of security of classical extractor constructions in the presence of quantum side information. We will first introduce the model and motivate it with some applications in quantum cryptography. We will then give an overview of those proof techniques that are known to extend, and those that are not yet known to extend. We will highlight some open questions.
References

The analysis of the "perfect matching extractor" presented in the talk can be found in this paper.

Security of 2universal hashing against quantum side information is
shown in the paper Leftover Hashing Against Quantum Side Information. See also Section 4.3 in Thomas's lecture notes. 
A paper on the first quantumproof nonmalleable extractor.
10:2511:45
A trio talk  under the hood of new extractor constructions
Eshan Chattopadhyay (IAS and Cornell University),
Gil Cohen (Princeton University and Tel Aviv University),
Xin Li (Johns Hopkins University)
slides for Part 1 given by Gil.
slides for Part 2 given by Xin
slides for Part 3 given by Eshan
The goal of this talk is to survey the "under the hood" of recent constructions of twosource and related types of extractors. In particular, we discuss nonmalleable extractors, resilient functions and newly defined primitives such as correlation breakers, and independentpreserving mergers.
References

Correlation breakers and the flipflop primitive can be found in this paper.

The paper that introduced independencepreserving mergers. Some of the improved constructions can be found here and, most recently, here.

There are more than a dozen papers about nonmalleable extractors. For earlier construction for high entropy see here and here. For lower minentropy see the first paper to achieve this, some general tools, and an improved construction.

The ChattopadhyayZuckerman twosource extractor for polylog entropy, and an improved reduction from twosource extractors to nonmalleable extractors due to BenAroya, Doron and TaShma.

See the original paper of Ajtai and Linial on resilient functions. The ChattopadhyayZuckerman paper has a derandomized construction. See also Meka's improved construction.

See this paper and references therein for nonmalleable codes.
Organizers: Eshan Chattopadhyay, Gil Cohen, Xin Li.
Workshop chairs: Avrim Blum, Yael Tauman Kalai.
.