Computer Science/Discrete Mathematics Seminar II | |

Topic: | Explicit two-source extractors and resilient functions II |

Speaker: | Eshan Chattopadhyay |

Affiliation: | University of Texas at Austin |

Date: | Tuesday, September 22 |

Time/Room: | 10:30am - 12:30pm/S-101 |

Video Link: | https://video.ias.edu/csdm/2015/0922-EshanChattopadhyay |

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 $\mathrm{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 David Zuckerman.