SCS Faculty Candidate

  • Gates Hillman Centers
  • ASA Conference Room 6115
  • RICHARD PENG
  • Assistant Professor
  • School of Computer Science
  • Georgia Institute of Technology
Talks

An Offline Approach to Efficient Algorithms

Over the past three decades, sophisticated mathematical tools were instrumental in many advances in algorithms. From an algorithmic perspective, these new tools are often used in ways akin to combinatorial data structures: with clear boundaries between their internal workings and the outer loops of the overall algorithm.

In the study of data structures, processing operations offline often leads to better performances than answering queries online as they arrive. In this talk, I will discuss how offline processing, or more simply, recursion, can also improve mathematical tools, and in turn motivate both new algorithms and new mathematical structures. I will overview progresses on problems motivated by combinatorial and scientific flows, draw connections with dynamic graphs as well as outreach activities, and describe recent works on speeding up Gaussian elimination.

Richard Peng is an assistant professor in the School of Computer Science at the Georgia Institute of Technology. His main research interests are in the design, analysis, and implementation of efficient algorithms. Over the past decade these interests revolved around problems induced by practice that arise at the intersection of discrete, numerical, and randomized algorithms. Results involving him obtained current best runtime bounds for: solving linear systems corresponding to random walks on undirected/directed graphs, maintaining approximate max-matchings in fully dynamic graphs, reducing the sizes of matrices while preserving L_1-norm structures, and approximating max-flows on undirected graphs. 

Richard received his BMath from the University of Waterloo in 2009, Ph.D. in Computer Science from CMU in 2013, and worked for two years as a postdoc/instructor in Applied Math at MIT. He was a Microsoft Research PhD Fellow, and his thesis received the CMU SCS Distinguished Dissertation Award. Richard is extensively involved with the organization of algorithmic problem solving related outreach activities, including working with a CMU team that won the North American Championship at the 2013 ACM International Collegiate Programming Contest. When not trying to solve problems, Richard enjoys baseball, hockey, and starcraft.

Faculty Host: Daniel Sleator (CSD)

 

For More Information, Please Contact: 
Keywords: