| 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.