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

Channel:
United States Simons Institute for the Theory of Computing
Subscribers:
68,700
Published on ● Video Link: https://www.youtube.com/watch?v=xft4foaV6fU


Duration: 1:12:22
2,275 views
45

Monika Henzinger (Institute of Science and Technology Austria (ISTA))
https://simons.berkeley.edu/events/dynamic-graph-algorithms-what-we-know-what-we-dont-richard-m-karp-distinguished-lecture
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.



Other Videos By Simons Institute for the Theory of Computing


2023-09-19Dynamic Matching: Rounding & Sparsification (And New Tools)
2023-09-19Parallel Batch-Dynamic Graph Representations
2023-09-19Dynamic Algorithms for 𝑘-center on Graphs
2023-09-19A Blackbox Reduction for Adaptive Adversaries using Differential Privacy
2023-09-19Recent Progress on Sublinear Time Algorithms for Maximum Matching: Upper Bounds
2023-09-18Parallelism in Dynamic Graph Algorithms
2023-09-18Optimizing Dynamic-Graph Data Structures on Multicores with the Locality-First Strategy
2023-09-18Recent Advances in Diversity Maximization in the Offline and Composable Coreset Models
2023-09-18Approximating Edit Distance in the Fully Dynamic Model
2023-09-18Lightning Talks
2023-09-12Dynamic Graph Algorithms: What We Know and What We Don’t | Richard M. Karp Distinguished Lecture
2023-09-08Probabilistic and Logical Circuits for Tractable Causal Reasoning
2023-09-08Probabilistic Reasoning and Learning for Trustworthy AI
2023-09-08Sampling and Approximately Counting CNF Formula Solutions in the Local Lemma Regime
2023-09-08Massively Parallel Join Algorithms
2023-09-08Relational Programming
2023-09-08Title: Research Interests and Latest Works
2023-09-08What can the demand analyst learn from machine learning?
2023-09-08From Robustness to Privacy and Back
2023-09-08Decoding the Maze: New Frontiers in Achieving Nash Equilibrium in AI Architectures
2023-09-08Risk Convergence and Algorithmic Regularization of Discrete-Stepsize (Stochastic) Gradient Descent


Tags:
Simons Institute
theoretical computer science
UC Berkeley
Computer Science
Theory of Computation
Theory of Computing
Richard M. Karp Distinguished Lecture
Monika Henzinger