Seminar • Algorithms and Complexity — Graph Algorithms and Batch Processing

Thursday, February 27, 2020 10:30 am - 10:30 am EST (GMT -05:00)

Richard Peng, School of Computer Science
Georgia Institute of Technology

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 discuss a method 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 allow for flexible notions of partial solutions. We illustrate this approach by discussing recent progress on two well-studied and foundational graph problems. In the first line of work, we developed almost-linear time algorithms for routing flow under a broad 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 handling large graphs and networks. His representative results include almost-linear time algorithms for wide classes of network flows, the current best data structures for maintaining a variety of quantities on 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.