CS Colloquium
Thursday, April 29, 2010
4:00 p.m., AKW 200

Host: Joan Feigenbaum

Sign up to meet with speaker.

Speaker: Moses Charikar, Princeton University
Title: Finding Dense Subgraphs

Abstract: The problem of finding dense subgraphs in a graph arises in a number of settings such as bioinformatics and the analysis of social networks. This problem has frustrated the development of good algorithms and yet resisted attempts to prove complexity theoretic lower bounds (although some versions are known to be efficiently solvable). Recently, assumptions that the problem is hard have been used to construct cryptosystems and establish the computational complexity of evaluating certain financial derivatives.

Variants of this problem have been shown to be closely connected to the Unique Games Conjecture that has been the recent focus of intense study in complexity theory. In this talk, I will survey some of the results that are known for the densest subgraph problem and present new algorithmic results for it. The new results (for worst case analysis) are inspired by studying an average case version of the problem and suggest a concrete distribution on inputs that seems out of reach for our current methods.

Bio: Moses Charikar is an Associate Professor of Computer Science at Princeton University. He received his undergraduate degree from the Indian Institute of Technology, Bombay in 1995 and his Ph.D. from Stanford University in 2000. He joined Princeton in 2001 after spending a year at Google Research.

He is broadly interested in the design and analysis of algorithms, with an emphasis on approximation algorithms for NP-hard problems, metric embeddings and algorithmic techniques for massive data sets.