# 2-Source Dispersers for Sub-Polynomial Min-Entropy and Ramsey Graphs Beating the Frankl Wilson Construction

 COMPUTER SCIENCE/DISCRETE MATH II Topic: 2-Source Dispersers for Sub-Polynomial Min-Entropy and Ramsey Graphs Beating the Frankl Wilson Construction Speaker: Anup Rao Affiliation: University of Texas Date: Tuesday, October 31 Time/Room: 10:30am - 12:30pm/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 \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.