Explicit Two-Source Extractors and Resilient Functions - David Zuckerman

From Katie Gentilello November 16th, 2016

11 plays 0 comments

We explicitly construct an extractor for two independent sources on n bits, each with min-entropy at least log^C n for a large enough constant C. Our extractor outputs one bit and has error n^{-\Omega(1)}. 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 function on n bits that is resilient to coalitions of size n^{1-delta}, for any delta>0. 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 polylog(n)-wise independently, and the remaining q=n^{1-\delta} bits are chosen by an adversary as an arbitrary function of the n-q bits. The best previous construction, by Viola, achieved q=n^{1/2 - \delta}. Our explicit two-source extractor directly implies an explicit construction of a 2^{(log log N)^{O(1)}}-Ramsey graph over N vertices, improving bounds obtained by Barak et al. and matching independent work by Cohen. Joint work with Eshan Chattopadhyay.
https://mediaspace.gatech.edu/media/zuckerman/1_rcdp0vnx

Tags: arc colloquiumalgorithms and randomness centergeorgia techrecorded by gtlibraryfall 2016

name: David Zuckerman
Date: November 14th, 2016
Appears In: Open Scholarship

Comments
Related Media

Loading…

Explicit Two-Source Extractors and Resilient Functions - David Zuckerman

Related Media