Wednesday, June 28, 2023
3:30 – 4:30 p.m. PT
Simons Institute for the Theory of Computing
Calvin Lab auditorium and Zoom

Richard M. Karp Distinguished Lecture

Jacob Fox (Stanford)

In the 1940s, Paul Erdős and Claude Shannon independently introduced probabilistic methods, revolutionizing combinatorics and information theory. Probabilistic methods have since had a profound impact on computer science and discrete mathematics.

A graph is Ramsey if the size of its largest clique or independent set is only logarithmic in the number of vertices. Erdős used probability to show that almost all graphs are Ramsey. Despite their ubiquitous nature, no explicit construction of Ramsey graphs is known. In this presentation, Jacob Fox will discuss progress on locating this "dark matter" of graphs, and connections to fundamental problems in information theory and additive combinatorics.

The Richard M. Karp Distinguished Lectures were created in Fall 2019 to celebrate the role of Simons Institute Founding Director Dick Karp in establishing the field of theoretical computer science, formulating its central problems, and contributing stunning results in the areas of computational complexity and algorithms. The series features visionary leaders in the field of theoretical computer science, and is geared toward a broad scientific audience.

Further event details are available here.

Light refreshments will be available prior to the start of the lecture.