SIGCOMM 2008

AUGUST 17-22
SEATTLE, WA, USA

Tutorial: Spectral Algorithms for Networks

Presented by: Santosh Vempala, Georgia Tech

Date: Sunday, August 17, 2008
Time: 0900-1500
Location: Stevens Room

Spectral methods are based on the principal components of input data. They have had much success in databases, information retrieval, image segmentation and unsupervised learning. In recent years, spectral methods have also been proposed to monitor networks for various types of anomalies such as unexpected or malicious behavior.

In this tutorial, we will go from the mathematics behind spectral methods to the latest advances in efficient algorithms. With the abundance of network data and the growth of networks, such algorithms are likely to play an important role in the near future. This tutorial will attempt to give a thorough introduction.

The slides from the tutorial are available here.

Outline

Part 1: Learning (0900-1030)

Part II: Clustering (1100-1230)

Part III: Sampling (1330-1430)

Solutions to exercises. (1430-1500)

About the presenter

Santosh Vempala is Distinguished Professor of Computer Science and Director of the Algorithms and Randomness Center (ARC ThinkTank) at Georgia Tech. His research interests are in algorithms, randomness and geometry and their applications. He graduated from CMU in 1997, advised by Avrim Blum and was at MIT until 2006 except for a year as a Miller Fellow at UC Berkeley. His book, "The Random Projection Method," was published in 2004 and another on "Spectral Algorithms" (with Ravi Kannan) is nearing completion. Vempala is a Sloan Fellow and a Guggenheim Fellow, and continues to get unreasonably excited when a phenomenon that appears complex from one perspective turns out to be simple from another.

Homepage: http://www.cc.gatech.edu/~vempala