-------------------------------------------------------------------------------
                   B O S T O N   U N I V E R S I T Y
                      Computer Science Department
                          C O L L O Q U I U M
                     Wednesday, December 13, 3:00 PM 
                       (Coffee served at 2:45PM)
                         Seminar Room / MCS 135

           Spectral Methods, Graph Partitioning, and Clustering

                              Shang-Hua Teng

                       Akamai Technologies Inc,  and
                       Department of Computer Science
                University of Illinois at Urbana-Champaign


  Spectral methods use eigenvectors of the underlying matrices for
  various combinatorial optimizations. Important applications include
  graph partitioning and clustering. While graph partitioning is an
  important component in circuit design and parallel numerical
  simulation,  clustering plays a role in large scale information
  organization.
  Spectral methods have been demonstrated by experiment to work
  extremely well. However, the quality of the solution that these
  methods  should produce had eluded precise analysis.

  In this talk, we show that the proper application of spectral
  partitioning techniques works well on bounded-degree planar graphs
  and finite element meshes---the classes of graphs to which they are
  usually applied. In particular, we prove that the eigenvector can be
  used to produce partitions whose ratio of vertices removed to edges
  cut  is $\O{\sqrt{n}}$ for bounded-degree planar graphs and
  two-dimensional meshes and $\O{n^{1/d}}$ for well-shaped
  $d$-dimensional meshes. The main ingredient of our analysis is a new
  geometric technique for estimating the second-smallest eigenvalues of
  the Laplacian matrices of these graphs. The locality that the
  spectral methods demonstrated in graph partition might potentially
  explain why they are effective in clustering.

  This is joint work with Daniel A. Spielman of MIT.

  Host:  Azer Bestravos