Explicit Ramsey Graphs and Two Source Extractors
CMSA Room G10 CMSA, 20 Garden Street, Cambridge, MA, United StatesSpeaker: 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, […]