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.