Title: Optimal extractors for generalized Santha-Vazirani sources

Abstract: Take a finite set of biased dice that share some common faces.  An adversary repeatedly tosses them, with each choice of die possibly depending on the previous outcomes.  Can you extract true randomness?  In 1986 Santha and Vazirani gave a negative answer when the dice are (two-sided) coins.  In 2015 Beigi, Etesami, and Gohari showed how to obtain an almost-unbiased bit for other sets of dice.  The sample complexity of their extractor is polynomial in the inverse of the error.

We completely classify all non-trivial randomness sources of this type into: (1) non-extractable ones; (2) extractable from polynomially many samples; and (3) extractable from an logarithmically many samples (in the inverse of the error).  The extraction algorithms are efficient and easy to describe.  I will discuss the relevance to distributed and cryptographic computation from imperfect randomness and point out some open questions in this context.

The talk is based on joint work with Salman Beigi, Omid Etesami, and Siyao Guo.