CSE Seminar or Event

An Offline Approach to Efficient Algorithms, Applied to Solving Linear Systems

Richard Peng

Assistant Professor
Georgia Tech
Wednesday, March 21, 2018
10:30am - 11:30am
3725 Beyster

Add to Google Calendar

About the Event

Solving a system of linear equations is one of the oldest and most well studied algorithmic problems. Linear system solvers have applications in diverse areas of computer science such as scientific computing, network science, and image processing. In this talk I will discuss recent progress on solvers for structured linear systems that led to nearly-linear time algorithms for analyzing random walks on directed graphs, as well as sub-quadratic time solvers for broader classes of linear systems.

These results stem from studying the structures of intermediate states of Gaussian elimination, which in turn allow for density reductions from adaptive sampling. This focus on intermediate algorithmic states is at the core of a highly fruitful approach for designing algorithms that examines interactions between algorithms and mathematical tools using ideas from offline data structures, or more simply, recursion. In the second half of this talk, I will briefly discuss these broader connections, and overview some extensions to numerical linear algebra, combinatorial optimization, and data structures.


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 include the 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 also has extensive involvements in algorithmic problem solving activities, including working with a CMU team that won the North American Champions at the 2013 ACM Intercollegiate Programming Contest. When not trying to solve problems, Richard enjoys baseball, hockey, and starcraft.

Additional Information

Sponsor(s): CSE

Open to: Public