2-source dispersers for n^o(1) entropy, and Ramsey graphs beating the Frankl-Wilson construction

Abstract

The main result of this paper is an explicit disperser for two independent sources on n bits, each of min-entropy k = 2 log n , where < 1 is some absolute constant. Put differently, setting N = 2 n and K = 2 k , we construct an explicit N N Boolean matrix for which no K K sub-matrix is monochromatic. Viewed as the adjacency matrix of a bipartite graph, this gives an explicit construction of a bipartite K-Ramsey graph of 2N vertices. This improves the previous bound of k = o(n) of Barak, Kindler, Shaltiel, Sudakov and Wigderson. As a corollary, we get a construction of a 2 n o(1) (nonbipartite) Ramsey graph of 2 n vertices, significantly improving the previous bound of 2 ( n) due to Frankl and Wilson.