Visible to the public Explicit Two-source Extractors and Resilient Functions

TitleExplicit Two-source Extractors and Resilient Functions
Publication TypeConference Paper
Year of Publication2016
AuthorsChattopadhyay, Eshan, Zuckerman, David
Conference NameProceedings of the Forty-eighth Annual ACM Symposium on Theory of Computing
Conference LocationNew York, NY, USA
ISBN Number978-1-4503-4132-5
KeywordsComputing Theory, graph theory, Human Behavior, malware analysis, Metrics, Pseudorandomness, pubcrawl, Ramsey graph, random key generation, Randomness Extractor, resilience, Resiliency, Resilient Function, Scalability, Two-Source Extractor

We explicitly construct an extractor for two independent sources on n bits, each with polylogarithmic min-entropy. Our extractor outputs one bit and has polynomially small error. The best previous extractor, by Bourgain, required each source to have min-entropy .499n. A key ingredient in our construction is an explicit construction of a monotone, almost-balanced Boolean functions that are resilient to coalitions. In fact, our construction is stronger in that it gives an explicit extractor for a generalization of non-oblivious bit-fixing sources on n bits, where some unknown n-q bits are chosen almost polylogarithmic-wise independently, and the remaining q bits are chosen by an adversary as an arbitrary function of the n-q bits. The best previous construction, by Viola, achieved q quadratically smaller than our result. Our explicit two-source extractor directly implies improved constructions of a K-Ramsey graph over N vertices, improving bounds obtained by Barak et al. and matching independent work by Cohen.

Citation Keychattopadhyay_explicit_2016