Erdős and Shannon: A Story of Probability, Communication, and Combinatorics | Richard M. Karp Distinguished Lecture

Abstract: 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.  

Jacob Fox has been a mathematics professor at Stanford University since 2015. Before joining Stanford, he was on the faculty at MIT. He received his PhD in math from Princeton University in 2010, after attending MIT as an undergraduate. Jacob was awarded the Oberwolfach Prize in 2016 for his outstanding contributions to discrete mathematics, and he won the Dénes König Prize in 2010 for new findings in Ramsey theory. His long history of work with Ramsey theory dates back to his high school years, when he won second place in the Intel Science Talent Search in 2002 for his mathematics project “Rainbow Ramsey Theory: Rainbow Arithmetic Progressions and Anti-Ramsey Results.”

===================================================================

Registration is not required for this event.

For those unable to attend in person, this lecture will be viewable via livestream on our YouTube channel: https://www.youtube.com/simonsinstitute

For directions to our building and for parking information, please visit: https://simons.berkeley.edu/directions

===================================================================

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. Formerly known as the Simons Institute Open Lectures, the series features visionary leaders in the field of theoretical computer science, and is geared toward a broad scientific audience. Light refreshments will be available prior to the start of the lecture. This lecture will be viewable thereafter on this page and on our YouTube channel.

The Simons Institute regularly captures photos and video of activity around the Institute for use in publications and promotional materials. 

If you require special accommodation, please contact our access coordinator at simonsevents [at] berkeley.edu with as much advance notice as possible.