Theory Talk

  • Gates Hillman Centers
  • ASA Conference Room 6115
  • Assistant Professor
  • School of Computer Science. Georgia Institute of Technology
  • and Visiting Researcher, Microsoft Research Redmond

Graph Algorithms and Batched Processing

Graphs, which in their simplest forms are vertices connected by edges, are widely used in scientific computing, machine learning and network science. This talk will use recent progresses on two well-studied graph problems, network flows and dynamic matchings, to discuss an approach for designing provably efficient graph algorithms. This approach revolves around the use of batched processing to combine graph theoretic approximations with iterative procedures that control the approximation errors.

I will start by describing how the study of vertex labeling problems and their duals, network flows, led to the study of residual graphs and convergences of successive approximations. I will then discuss a similar phenomenon in dynamic graph data structures, where vertex reductions allow the maintenance of large matchings in graphs undergoing edge insertions/deletions. A key idea at the core of these results is the replacement of natural online path finding schemes by ones that find batches of paths.

Richard Peng is an assistant professor in the School of Computer Science at the Georgia Institute of Technology, and a visiting researcher (in MLO) at Microsoft Research Redmond.  His research interests are in the design, analysis, and implementation of efficient algorithms. He received a BMath from Waterloo, PhD from CMU, and was a postdoc at MIT. Awards include the NSF Career Award, Microsoft Research PhD Fellowship, and CMU SCS Distinguished Dissertation Award.  Richard is extensively involved with algorithmic problem solving based outreach activities such as the IOI, the DMOJ Online Judge.

Faculty Host: Daniel Sleator

For More Information, Please Contact: