2-Source Dispersers for n^{o(1)} Entropy, and Ramsey Graphs Beating theFrankl-Wilson Construction

COMPUTER SCIENCE/DISCRETE MATH I
Topic:	2-Source Dispersers for n^{o(1)} Entropy, and Ramsey Graphs Beating theFrankl-Wilson Construction
Speaker:	Anup Rao
Affiliation:	University of Texas
Date:	Monday, October 30
Time/Room:	11:15am - 12:15pm/S-101

---

The main result of this work is an explicit disperser for two independent sources on n bits, each of entropy k=n^{o(1)}. Put differently, setting N=2^n and K=2^k, we construct explicit N by N Boolean matrices for which no K by K submatrix is monochromatic. Viewed as adjacency matrices of bipartite graphs, this gives an explicit construction of K-Ramsey bipartite graphs of size N.

This greatly improves the previous the previous bound of k=o(n) of Barak, Kindler, Shaltiel, Sudakov and Wigderson. It also significantly improves the 25-year record of k= \tilde O(\sqrt{n}) on the very special case of Ramsey graphs, due to Frankl and Wilson.

Another result in this paper which is interesting on its own is a construction of a new independent sources extractor that can extract from a constant number of sources of polynomially small min-entropy with exponentially small error. This improves a result of Rao \cite{Rao06}, which only achieves polynomially small error.

This is joint work with Boaz Barak, Ronen Shaltiel and Avi Wigderson.