Title: Semidefinite Programming and Approximation Algorithms: A Survey of Recent Results  
Name: Sanjeev Arora Princeton University 

Time:October 13th (Monday) 14:0014:45  
Location: Lecture Hall, FIT Building, Tsinghua University  
Host Unit: ITCS, Tsinghua University 
Computing approximately optimal solutions is an attractive way to cope with NPhard optimization problems. In the past decade or so, semidefinite programming or SDP (a form of convex optimization that generalizes linear programming) has emerged as a powerful tool for designing such algorithms, and the last few years have seen a profusion of results (worstcase
algorithms, average case algorithms, impossibility results, etc).
This talk will be a survey of this area and these recent results. We will see that analysing semidefinite program draws upon ideas from a variety of other areas, and has also led to new results in Mathematics. At the end we will touch upon work that greatly improves the running time of SDPbased algorithms, making them potentially quite practical.
The survey will be essentially selfcontained.
Sanjeev Arora is Professor of Computer Science at Princeton University and works in computational complexity theory, approximation algorithms for NPhard problems, geometric algorithms, and probabilistic algorithms. He has received the ACM Doctoral Dissertation Award, the SIGACTEATCS Goedel Prize, and the Packard Fellowship.