Return to Colloquia & Seminar listing
Explicit Two Source Extractors and Ramsey Graphs
Joint Math/CS Theory| Speaker: | David Zuckerman, UT Austin |
| Location: | 1131 Kemper |
| Start time: | Mon, Nov 9 2026, 4:10PM |
Description
Randomness is extremely useful in computing, but typical sources of randomness are extremely defective. In this talk, I'll discuss our exponential improvement in extracting randomness from two independent low-quality sources, as well as more recent developments. I'll also describe an application to Ramsey theory. Specifically, we explicitly construct graphs with no large cliques or independent sets.
Based on joint work with Eshan Chattopadhyay.