A Survey on Dynamic Graph Algorithms and Complexity

In this talk I will survey exciting past progresses and future opportunities in developing algorithms and complexity theory for dynamic graph problems. I will discuss barriers and intermediate steps in resolving some of the central graph problems in the area, such as connectivity, minimum spanning tree, shortest paths, minimum cut, and maximum matching. I will also discuss how ideas and techniques from other areas – such as spectral method, sketching, algebraic techniques, primal/dual method, and distributed/parallel algorithms – came into play in developing dynamic graph algorithms.