The main result of this paper 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= O(\sqrt{n}) on the
very special case of Ramsey graphs, due to Frankl and Wilson.
The construction uses (besides "classical" extractor ideas) almost
all of the machinery developed in the last couple of years for
extraction from independent sources.
