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 half-day 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:45-11:45.
Location: Bradbury/Rose, Omni Hotel, LA.
8:45-9:15
Randomness Extractors: An Introduction
David Zuckerman (UT Austin)
A randomness extractor is an efficient algorithm that extracts high-quality randomness from a low-quality random source. We examine when such randomness extraction is possible, surveying seeded, seedless, and multi-source extractors.
9:15-9: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 Ta-Shma's thesis for the origin of mergers.
9:45-10:15
Quantum-proof 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 2-universal 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 quantum-proof non-malleable extractor.
10:25-11: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 two-source and related types of extractors. In particular, we discuss non-malleable extractors, resilient functions and newly defined primitives such as correlation breakers, and independent-preserving mergers.
References
-
Correlation breakers and the flip-flop primitive can be found in this paper.
-
The paper that introduced independence-preserving mergers. Some of the improved constructions can be found here and, most recently, here.
-
There are more than a dozen papers about non-malleable extractors. For earlier construction for high entropy see here and here. For lower min-entropy see the first paper to achieve this, some general tools, and an improved construction.
-
The Chattopadhyay-Zuckerman two-source extractor for poly-log entropy, and an improved reduction from two-source extractors to non-malleable extractors due to Ben-Aroya, Doron and Ta-Shma.
-
See the original paper of Ajtai and Linial on resilient functions. The Chattopadhyay-Zuckerman paper has a derandomized construction. See also Meka's improved construction.
-
See this paper and references therein for non-malleable codes.
Organizers: Eshan Chattopadhyay, Gil Cohen, Xin Li.
Workshop chairs: Avrim Blum, Yael Tauman Kalai.
.