Dynamic Graph Algorithms: What We Know and What We Don’t | Richard M. Karp Distinguished Lecture

A dynamic graph algorithm is a data structure that maintains information about a graph while it is modified through local operations such as edge or vertex insertions or deletions. These data structures can be used in real-world applications such as maintaining clusters in large social networks or as subroutines in static graph algorithms.

The research on designing efficient dynamic graph algorithms started in the 1980s, and in past years has become a popular research field as dynamic graph algorithms are a critical component in recent breakthrough results in static graph algorithms, for example, in the almost-linear time algorithms for maximum flow and minimum-cost flow. In this presentation, Monika Henzinger will survey the state of the art in dynamic graph algorithms, the different algorithmic techniques developed for them, and all the questions in the field that still await an answer.

Monika Henzinger is a professor at the Institute of Science and Technology Austria (ISTA). In her prior career, she was a professor at the University of Vienna, a professor at EPFL in Switzerland, and a director of research at Google. She is a fellow of the ACM and the EATCS and a member of the Austrian Academy of Sciences, and she has received two ERC Advanced Grants, as well as the Wittgenstein-Preis, the highest science award in Austria.

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

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.