![Loading Events](https://cmsa.fas.harvard.edu/wp-content/plugins/the-events-calendar/src/resources/images/tribe-loading.gif)
- This event has passed.
Explicit Ramsey Graphs and Two Source Extractors
October 21, 2022 @ 11:00 am - 12:00 pm
![](https://cmsa.fas.harvard.edu/media/CMSA-Member-Seminar-10.21.22.png)
Speaker: David Zuckerman, Harvard CMSA/University of Texas at Austin
Title: Explicit Ramsey Graphs and Two Source Extractors
Abstract: Ramsey showed that any graph on N nodes contains a clique or independent set of size (log N)/2. Erdos showed that there exist graphs on N nodes with no clique or independent set of size 2 log N, and asked for an explicit construction of such graphs. This turns out to relate to the question of extracting high-quality randomness from two independent low-quality sources. I’ll explain this connection and our recent exponential improvement in constructing two-source extractors.