Randomness extraction is a fundamental problem that has been studied for over three decades, where the goal is to harvest uniform bits from weak sources of randomness. A well-studied setting assumes that one has access to multiple independent weak random sources, each with some entropy. However, this assumption is often unrealistic in practice. In real life, natural sources of randomness can produce samples with no entropy at all or with unwanted dependence.
Motivated by this and applications in cryptography, we introduce a class of distributions called "adversarial sources," and we construct randomness extractors for this new setting. The class of adversarial sources generalizes several previously studied settings, and as a result we obtain improved extractors for distributions sampled by algorithms of low (space) complexity. Our constructions combine recent tools from extractor theory through various sorts of explicit extremal hypergraphs, which are built using recent advances in combinatorics (cap set bounds, explicit Ramsey graphs).
Joint work with Eshan Chattopadhyay, Vipul Goyal, and Xin Li.
Please email Anton Bernshteyn (abernsht ~at~ math.cmu.edu) for a password.
The ACO Seminar (2019–2020)