Explicit Ramsey Graphs and Two Source Extractors

Name: Explicit Ramsey Graphs and Two Source Extractors
Start: 2022-10-21T11:00:00-04:00
End: 2022-10-21T12:00:00-04:00
Location: CMSA, 20 Garden St, G10

CMSA EVENTS: CMSA MEMBER SEMINAR

When: October 21, 2022

11:00 am - 12:00 pm

Where: CMSA, 20 Garden St, G10

Address: 20 Garden Street, Cambridge, MA 02138, United States

Speaker: David Zuckerman - Harvard CMSA/The University of Texas at Austin

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.

This seminar will begin at 11:00am and lunch will follow at 12:00pm.