[Colloq] REMINDER: Colloquium - Moses Charikar, Princeton University TODAY 11:30

[Rachel Kalweit]

The College of Computer and Information Science Colloquium Presents a talk by:

Prof Moses Charikar
CS, Princeton

Wednesday, March 25, 2009
11:30am
366 West Village H

Title:
"New Insights into Semidefinite Programming for Combinatorial Optimization"

Abstract:
Beginning with the seminal work of Goemans and Williamson on Max-Cut, semidefinite programming (SDP) has firmly established itself as an important ingredient in the toolkit for designing approximation algorithms for NP-hard problems. Algorithms designed using this approach produce configurations of vectors in high dimensions which are then converted into actual solutions.

In recent years, we have made several strides in understanding the power as well as the limitations of of such SDP approaches. New insights into the geometry of these vector configurations have led to algorithmic breakthroughs for several basic optimization problems. At the same time, a sequence of recent results seems to suggest the tantalizing possibility that, for several optimization problems including Max-Cut, SDP approaches may indeed be the best possible. In this talk, I will present a glimpse of some of this recent excitement around SDP-based methods and explain some of the new insights we have developed about the strengths and weaknesses of this sophisticated tool.

Bio:
Moses finished his PhD in Computer Science from Stanford University in the summer of 2000.  He joined the Computer Science department at Princeton in Fall 2001, after spending a year in the research group at Google. Before attending graduate school at Stanford, he was an undergraduate at the Indian Institute of Technology at Bombay (now Mumbai), which is also the city where he was born and grew up in.  
His interests are in theoretical computer science. 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.

_______________________________________________
Colloq mailing list
Colloq at lists.ccs.neu.edu
https://lists.ccs.neu.edu/bin/listinfo/colloq