Algorithmic Paradigms for Dynamic Graphs

In the traditional view of computation, a computational task is solved from scratch, and then remains solved forever. It is increasingly clear that this static model does not adequately capture the requirements of real-world computation. For instance, in a communication network, new links appear and disappear all the time. Recomputing everything from scratch (to obtain, for instance, connectivity-information about the network) is clearly wasteful. Similar dynamic scenarios arise in most modern applications, including load balancing in parallel computation, tracking communities in social networks, financial fraud detection, and routing. Dynamic graph algorithms aim to address this issue; they maintain information about graphs that undergo edge/vertex updates without recomputing everything from scratch after each update. These algorithms are promising for all the practical applications mentioned above and have deep theoretical applications. Unfortunately, even the most basic graph problems, such as graph connectivity and shortest paths, are still not well-understood in the dynamic setting.

In this talk, I will talk about two general techniques that can be used to break decades-old barriers on many dynamic graph problems: 1) dynamic expander decomposition and 2) local clustering.
The new development of these techniques on dynamic graphs, in turn, leads to exciting applications even in the classical static setting. For example, they break the 50-year-old quadratic time bound for checking k-vertex-connectivity to nearly linear time.

Bio: Thatchaphol Saranurak is a theoretical computer scientist, currently holding a research assistant professor position at Toyota Technological Institute at Chicago, USA. He completed his Ph.D. at KTH Royal Institute of Technology in 2018 where he was supervised by Danupon Nanongkai. His main research interest is on graph algorithms with a current focus on dynamic, local, and distributed algorithms.

11:30-Noon: Grad Student Round Table with the Candidate, 3725 Beyster