Computer Science/Discrete Mathematics Seminar II

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 \times N$ Boolean matrices for which no $K \times K$ submatrix is monochromatic. Viewed as adjacency matrices of bipartite graphs, this gives an explicit construction of $K$-Ramsey {\em bipartite} graphs of size $N$. Our disperser is obtained by generalizing the Challenge-Response Mechanism of \cite{BarakKSSW05} so that we can apply it in a recursive manner to \emph{find} the min-entropy concentrations in a source of low min-entropy. This is joint work with Boaz Barak, Ronen Shaltiel and Avi Wigderson.