Computer Science/Discrete Mathematics Seminar I

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.