TIME: 1:30-2:20 pm, October 30, 2007 PLACE: CSE 503 SPEAKER: Satyen Kale Microsoft Research TITLE: A Combinatorial, Primal-Dual Approach to Semidefinite Programs ABSTRACT: Algorithms based on convex optimization, especially linear and semidefinite programming, are ubiquitous in Computer Science. While there are polynomial time algorithms known to solve such problems, quite often the running time of these algorithms is very high. Designing simpler and more efficient algorithms is important for practical impact. In my talk, I will describe applications of a Lagrangian relaxation technique, the Multiplicative Weights Update method in the design of efficient algorithms for various optimization problems. We generalize the method to the setting of symmetric matrices rather than real numbers. The new algorithm yields the first truly general, combinatorial, primal-dual method for designing efficient algorithms for semidefinite programming. Using these techniques, we obtain significantly faster algorithms for approximating the Sparsest Cut and Balanced Separator in both directed and undirected weighted graphs to factors of O(log n) and O(sqrt{log n}), and also for the Min UnCut and Min 2CNF Deletion problems. The algorithm also has applications in quantum computing and derandomization. This is joint work with Sanjeev Arora.