SCS Faculty Recruit Seminar - Richard Peng - Multifaceted Algorithm Design via Graph Laplacians

Event Details
  • Date/Time:
    • Tuesday February 10, 2015
      10:00 am - 11:30 am
  • Location: Klaus Classroom 2447
  • Phone:
  • URL:
  • Email:
  • Fee(s):
    0.00
  • Extras:
Contact

Essie M. Reynolds

ereynold@cc.gatech.edu

Summaries

Summary Sentence: SCS Faculty Recruit Seminar - Multifaceted Algorithm Design via Graph Laplacians

Full Summary: No summary paragraph submitted.

Media
  • Richard Peng Richard Peng
    (image/jpeg)

Richard Peng is an Instructor in Applied Mathematics at MIT. His main research interestes are in the design of methods that provably solve large problems quickly. Richard received his Ph.D. from Carnegie Mellon University in 2013. He was a Microsoft Research Ph.D. Fellow and his thesis won the CMU SCS Distinguished Dissertation Award. 

Abstract:

Many computational problems induced by practice arise at the intersection of combinatorics, optimization and statistics. Combining insights from these areas often leads to better algorithms for such problems, as well as improvements to these areas themselves. In this talk, I will discuss some recent progress via this approach:
* A fast solver for linear systems involving graph Laplacians, a core primitive in spectral algorithms and a well-studied routine in scientific computing.
* The first O(m polylog(n)) time algorithm for approximating undirected maximum flows,  a fundamental problem in combinatorial optimization.
* The first nearly optimal subsampling algorithms that preserve the L_1-norms of matrix-vector products, a common structure in data analysis.
These algorithms rely on connections between iterative methods, flows, and sampling drawn through the Laplacian matrices of undirected graphs. Components that may be of independent interest include an algorithmic framework based on sparsified matrix squaring, the chicken-and-egg problem of building/utilizing high quality approximations, and extensions of matrix concentration bounds to general p-norms.

Additional Information

In Campus Calendar
No
Groups

College of Computing, School of Computer Science

Invited Audience
Undergraduate students, Faculty/Staff, Public, Graduate students
Categories
Seminar/Lecture/Colloquium
Keywords
Georgia Tech College of Computing, MIT, Richard Peng, School of Computer Science, SCS
Status
  • Created By: Birney Robert
  • Workflow Status: Published
  • Created On: Jan 27, 2015 - 7:16am
  • Last Updated: Apr 13, 2017 - 5:20pm