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.