TIME: 1:30-2:30 pm,  Tuesday, September 30, 2008

PLACE: CSE 503  

SPEAKER: Dan Spielman
         Yale University

TITLE: Graph approximation and local clustering, with applications to
       the solution of diagonally-dominant systems of linear equations


ABSTRACT:
We discuss several fascinating concepts and algorithms in graph theory
that arose in the design of a nearly-linear time algorithm for solving
diagonally-dominant linear systems.  We begin by defining a new notion
of what it means to approximate a graph by a sparser or smaller graph,
and explain why these sparse approximations enable the fast solution
of linear equations.  To build these sparsifiers, we rely on
low-stretch spanning trees, random matrix theory, spectral graph
theory, and graph partitioning algorithms.

The need to quickly partition a graph leads us to the local clustering
problem: given a vertex in a massive graph,  output a small cluster
near that vertex in time proportional to the size of the cluster.

We use all these tools to design nearly-linear time algorithms for
solving diagonally-dominant systems of linear equations, and give some
applications.

This talk focuses on joint work with Shang-Hua Teng, and touches on
work by Vaidya, Gremban, Miller, Koutis, Emek, Elkin, Andersen, Chung,
Lang, Daitch, Srivastava and Batson.