CS - 596 : Topics In The Foundations Of Computer Science (Semidefinite Programming)
Spring 2008

Place: 254 Hill Center
Time: Wednesdays 3:20 -- 6:20 pm
Instructor: Mario Szegedy, szegedy@cs, 446 Hill Center, Tel. 445-4184
TA: Devendra Desai, devdesai@cs, 203 Hill Center, Tel. 445-2001 Ext. 9542

Course description:

In this course we will study the field of Semidefinite Programming (SDP), which is a subfield of Convex Optimization. SDP deals with optimization problems over symmetric positive semidefinite matrix variables with linear cost function and linear constraints. We will study the theory of SDPs, efficient ways to solve them (eg. the interior point method) and various applications of SDPs to computer science.

Papers discussed in class:

• The sandwich theorem - D. E. Knuth.
• Approximate graph coloring by semidefinite programming - D. Karger, R. Motwani and M. Sudan.
• Semidefinite Optimization - M. Todd.
• Papers on SDPs for Unique Games:
  • On the power of unique 2-prover 1-round games - S. Khot.
  • Near-optimal algorithms for unique games - M. Charikar, K. Makarychev and Y. Makarychev.
• Expander Flows, Geometric Embeddings, and Graph Partitionings - S. Arora, S. Rao and U. Vazirani [shorter version].
• Integrality Gaps for Sparsest Cut and Minimum Linear Arrangement Problems - N. Devanur, S. Khot, R. Saket and N. Vishnoi.

References:

• Randomized graph products, chromatic numbers, and the Lovász theta-function - U. Feige.
• Improved Approximation Algorithms for Maximum Cut and Satisfiability Problems Using Semidefinite Programming - M. Goemans and D. Williamson.
• A note on the theta number of Lovász and the generalized Delsarte bound - M. Szegedy.
• Semidefinite Programming - L. Vandenberghe and S. Boyd (Survey article).

Other SDP resources:

• Semidefinite Programming / Semidefinite Optimization - Christoph Helmberg's page giving links to introductions and events in the field.
• Some papers on semidefinite programming - F. Alizadeh's SDP page.