Abstract: Network structures are ubiquitous in operations research, high performance computing, databases, and machine learning. Recent growth in the scale of graph data is making it increasingly important to have provably efficient algorithms for large, often dynamically changing, graphs. This talk will survey some key ideas behind recent theoretical progress in max-flow and dynamic connectivity, as well as practical improvements to optimal transport and graph embeddings. The key idea in this method for designing faster graph algorithms and data structures is to keep all intermediate structures as graphs.

These intermediate graphs in turn lead to subproblems that are more robust to approximations and partial progresses. We illustrate this approach by discussing recent progress on two well-studied graph problems. In the first line of work, we give almost-linear time algorithms for routing flow in a network subject to a wide family of cost functions, and in the second line of work, we gave the first worst-case sub-polynomial time deterministic data structure for maintaining connectivity in a graph undergoing edge insertions and deletions.

Bio: Richard Peng is an assistant professor in the School of Computer Science at the Georgia Institute of Technology. His research interests are in the design, analysis, and implementation of efficient algorithms, with a focus on algorithms and data structures for large graphs.  His representative results include almost-linear time algorithms for wide classes of network flows, sparsification based data structures for maintaining dynamically changing graphs, and solvers for graph-structured linear systems.

Richard received his BMath from Waterloo, his PhD from CMU, and was a postdoc at MIT. He has received the NSF Career Award, the Microsoft Research PhD Fellowship, and the CMU SCS Distinguished Dissertation Award. Richard has extensive involvements with algorithmic problem solving based outreach activities, including the recent organization of the North America Programming Camp for students participating in the International Collegiate Programming Contest (ICPC). In his spare time, Richard enjoys baseball, hockey, and studying StarCraft AIs.