[Colloquium] Talk by Prasad Raghavendra, University of Washington on February 3, 2009

[Katie Casey]

DEPARTMENT OF COMPUTER SCIENCE

UNIVERSITY OF CHICAGO

Date: Tuesday, February 3, 2009
Time: 2:30 p.m.
Place: RY 251

----------------------------------------------------------

Speaker:	Prasad Raghavendra

From:		University of Washington

Website:		http://www.cs.washington.edu/homes/prasad/

Title:    Approximating the Optimum: Efficient Algorithms and their  
Limits

Abstract:    Most combinatorial optimization problems of interest are  
NP-hard to solve exactly. To cope with this intractability, one  
settles for approximation algorithms with provable guarantee on the  
quality of approximation. Despite great success in designing  
approximation algorithms, underlying a vast majority of the work is  
the technique of linear programming, or more generally semi-definite  
programming. This poses the natural question: How far can we push the  
technique of semi-definite programming? Are these techniques that  
yield better approximations than semi-definite programming?
In this work, we show that the simplest semi-definite programs yield  
the best approximation for large classes of optimization problems  
ranging from constraint satisfaction problems (CSP) to graph labeling  
problems, ordering CSPs to certain clustering problems, under the  
Unique Games Conjecture. In a surprising convergence of algorithms and  
hardness results, the same work also leads to a generic algorithm that  
achieves the optimal approximation for every constraint satisfaction  
problem.

Bio:

Prasad Raghavendra obtained his bachelor’s degree at Indian Institute  
of Technology, Madras, and is currently a PhD candidate at University  
of Washington. His research interests include several areas of  
theoretical computer science such as approximation algorithms and  
inapproximability results for NP-hard optimization problems, error  
correcting codes, metric embeddings, computational learning and  
complexity. He is the recipient of the Best Paper and Best Student  
Paper awards at STOC ’08.


Refreshments will be served following the talk in RY 255 at 3:30.