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)

slides

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)

slides

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

9:45-10:15

Quantum-proof extractors: definition, constructions, applications, and open questions

Thomas Vidick (California Institute of Technology)

slides

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

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

Organizers: Eshan Chattopadhyay, Gil Cohen, Xin Li.

Workshop chairs: Avrim Blum, Yael Tauman Kalai.

.