[Colloquium] TIME CHANGE: Talk by Prasad Raghavendra

[Katie Casey]

DEPARTMENT OF COMPUTER SCIENCE

UNIVERSITY OF CHICAGO

Date: Tuesday, February 3, 2009
Time: 3:00 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 4:00.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://mailman.cs.uchicago.edu/pipermail/colloquium/attachments/20090130/ab4943c0/attachment.htm