Loading Events

« All Events

  • This event has passed.

Explicit Ramsey Graphs and Two Source Extractors

October 21, 2022 @ 11:00 am - 12:00 pm

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.

Details

Date:
October 21, 2022
Time:
11:00 am - 12:00 pm
Event Category:

Venue

CMSA Room G10
CMSA, 20 Garden Street
Cambridge, MA 02138 United States
+ Google Map
Phone:
6174967132