New Perspectives on Classic Questions in the Theory of Graph Algorithms

Abstract: The theory of graph algorithms is a research field that develops clever mathematical techniques with provable guarantees to eventually make computing devices process graph (network) data with less resource such as time, energy, and hardware. Despite its pivotal role in computer science over many decades, the theory of graph algorithms research still lacks techniques for designing efficient algorithms for some of the most basic tasks, and for exploiting technological advances from the last few decades: On the one hand, the ever-increasing data volumes call for nearly-linear time algorithms which are still elusive for many basic problems. On the other hand, to exploit advances in computer architecture and large-scale systems, we need algorithms that are efficient in models of computation beyond the classic sequential setting.

In this talk, I will discuss some recent progress towards nearly-linear time algorithms and efficient algorithms across many computational models such as dynamic graphs, distributed networks, and streaming algorithms. Basic graph problems that will be discussed include cut, matching, and shortest paths. Techniques that will be reviewed at a very high level include expander decomposition and some spectral techniques. No background is required, although familiarity with basic graph terminologies and algorithms will be useful.

Bio: Danupon Nanongkai is currently an associate professor in the Theoretical Computer Science division at KTH Royal Institute of Technology, Sweden. He received a Ph.D. in Algorithms, Combinatorics, and Optimization (ACO) from Georgia Tech in 2011 and a docent in Computer Science from KTH in 2017. He was awarded the Principles of Distributed Computing Doctoral Dissertation Award in 2013 and the ERC Starting Grant in 2016. His research interest is generally on graph algorithms and complexity, where the current focus is on distributed, dynamic, and sequential graph algorithms. His results include the first progress in many decades for some fundamental graph-algorithmic questions.