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.