[Colloquium] REMINDER: Distinguished Lecture Series: Luca Trevisan, UC Berkeley

[Dawn Ellis]

Monday, November 3, 2014 at 11:00 am
TTIC
6045 S. Kenwood Ave.
Room #526​

*Luca Trevisan*, Professor, Computer Science Division and Simons Institute
for the Theory of Computing, U.C. Berkeley

Homepage <http://www.cs.berkeley.edu/~luca>

*Title:* Graph Partitioning Algorithms and Laplacian Eigenvalues

*Abstract:* Spectral graph theory studies applications of linear algebra to
graph theory and to the design and analysis of graph algorithms. "Spectral"
graph algorithms are algorithms that exploit properties of the eigenvalues
and eigenvectors of matrices associated with a graph, such as the Laplacian
matrix. Spectral partitioning and clustering algorithms usually work well
in practice, but the theory still gives only an incomplete rigorous
understanding of their performance. We report on some progress in this
direction.

The Cheeger inequality is a classical result in spectral graph theory which
states that the second Laplacian eigenvalue of a graph is small if and only
if the graph has a sparse cut. The proof of the Cheeger inequality also
 gives a worst-case analysis of the "sweep" spectral partitioning algorithm
of Fiedler as an approximation algorithm for the sparsest cut problem.

We discuss three generalizations of this result:
(i) the k-th Laplacian eigenvalue is small if and only if the vertices can
be partitioned into k subsets, each defining a sparse cut.
(ii) if the k-th Laplacian eigenvalue is large, then  Fiedler's sweep
algorithm performs better than the worst-case bounds implied by Cheeger's
inequality. This gives an explanation for the good performance of Fiedler's
algorithm for some types of graphs.
(iii) if the k-th Laplacian eigenvalue is small and the (k+1)-st is large,
then the vertices can be partitioned into k subsets such that each subset
defines a sparse cut and each subset induces an expanding subgraph. This
points to a rigorous justification for the good performance of spectral
clustering algorithms.

*Bio:* Luca Trevisan is a professor of electrical engineering and computer
science at U.C. Berkeley and a senior scientist at the Simons Institute for
the Theory of Computing. Luca received his Dottorato (PhD) in 1997, from
the Sapienza University of Rome, working with Pierluigi Crescenzi. After
graduating, Luca was a post-doc at MIT and at DIMACS, and he was on the
faculty of Columbia University, U.C. Berkeley, and Stanford, before
returning to Berkeley in 2014.

Luca's research is in theoretical computer science, and most of his work
has been in two areas: (i) pseudo-randomness and its relation to
average-case complexity and derandomization; and (ii) the theory of
probabilistically checkable proofs and its relation to the approximability
of combinatorial optimization problems. In the past three years he has been
working on spectral graph theory and its applications to graph algorithms.

Luca received the STOC'97 Danny Lewin (best student paper) award, the 2000
Oberwolfach Prize, and the 2000 Sloan Fellowship. He was an invited speaker
at the 2006 International Congress of Mathematicians in Madrid.

Host:  Madhur Tulsiani,  madhurt at ttic.edu



-- 
*Dawn Ellis*
Administrative Coordinator,
Bookkeeper
773-834-1757
dellis at ttic.edu

TTIC
6045 S. Kenwood Ave.
Chicago, IL. 60637
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://mailman.cs.uchicago.edu/pipermail/colloquium/attachments/20141031/9b896f26/attachment.htm