Skip to main navigation
Skip to Content
Computer Science
University of Toronto
U of T Portal
Student Support
Contact
About
Why Study CS at U of T
Career Options
History of DCS
Giving to DCS
Computer Science at UofT Mississauga
Computer Science at UofT Scarborough
Contact
Employment Opportunities for Faculty/Lecturers
How to Find Us
Undergraduate
Prospective Undergraduates
Current Undergraduates
Graduate
Prospective Graduate students
Current Graduate students
Research
Research Areas
Partner with us
People
Faculty
Staff
In Memoriam
Alumni and Friends
Honours & Awards
Women in Computer Science
Graduate Student Society
Undergraduate Student Union
Undergraduate Artificial Intelligence Group
Undergraduate Theory Group
News & Events
News
Events
Newsletter: @DCS Update
Alumni
Donate
You are viewing: >
Home
>
News & Events
>
Events
> Theory Seminar - November 25
About
Undergraduate
Graduate
Research
People
News & Events
Theory Seminar - November 25
Event date: Friday, November 25, 2011, at 11:10 AM
Location: BA1240
SPEAKER: Richard Peng
Department of Computer Science
Carnegie Mellon University
TITLE: Algorithm Design Using Spectral Graph Theory
ABSTRACT:
Spectral Graph Theory is the interplay between linear algebra and combinatorial graph theory. One application of this interplay is fast solvers for symmetric diagonally dominant (SDD) linear systems, which occur ubiquitously in combinatorial optimization, computer vision, computer graphics and machine learning.
This talk will present an algorithm for solving SDD linear systems with m non-zero entries to an error of at most epsilon in O(m log n log(1/epsilon)) expected time. The solver algorithm is based on a multitude of tools developed over the past decade. At the heart of it is an algorithm that efficiently finds a chain of increasingly sparser graphs that are spectrally 'equivalent', which may be of independent interest.
I will also describe recent work on using the solver for total variation minimization and undirected multicommodity flow. As well as mention results about speeding up and parallelizing one of the key underlying routines.
Topics in this talk represent joint work with Guy Blelloch, Anupam Gupta, Jon Kelner, Yiannis Koutis, Aleksander Madry, Gary Miller and Kanat Tangwongsan.