[talks] E Chlamtac preFPO

[Melissa M Lawson]

Eden Chlamtac will present his preFPO on Tuesday, March 4, at 4:30PM in Room 402.  The
members of his committee are Sanjeev Arora (advisor), Moses Charikar and Bernard Chazelle
(readers), and Boaz Barak and Ken Steiglitz (non-readers).  Everyone is 
invited to attend his talk.  His abstract follows below.
-------------------------------------------------

Title: Non-Local Analysis of SDP-Based Approximation Algorithms

Abstract:

Semidefinite Programming (SDP) has been at the core of many approximation algorithms since
the seminal work of Goemans and Williamson on MAX-CUT. 
Analysis of the approximation guarantee afforded by SDP-based approximation algorithms has
traditionally relied on a comparison of local random events to corresponding local
structures in the input. A marked departure from this approach was demonstrated recently
in the work of Arora, Rao, and Vazirani on SPARSEST CUT, where a more nuanced
probabilistic argument was used to combine local random events, thus yielding an improved
approximation guarantee.

I will describe a number of SDP-based algorithms which admit a non-local analysis of their
approximation guarantee. In one case, the analysis is inspired by the approach of
Arora-Rao-Vazirani, while in other cases, both the algorithm and the analysis make novel
use of SDP hierarchies. These hierarchies give progressively tighter relaxations of
combinatorial problems. Previously they had been shown not to yield any significant
improvement in the approximation of various important problems, thus the results I will
discuss mark a first positive use of these hierarchies.

In particular, I will describe the following results:

1. A proof that the algorithm of Blum and Karger for coloring 3-colorable graphs yields a
legal coloring using at most O(n^0.2130) colors (as opposed to the original guarantee of
O(n^0.2142)).

2. An algorithm for coloring 3-colorable graphs which yields a legal coloring using at
most O(n^0.2072) colors. This algorithm extends that of Blum-Karger, and uses the third
level of the Lasserre SDP hierarchy.

3. An approximation algorithm which finds an independent set of size
n^poly(gamma) in any 3-uniform hypergraph which contains an independent set of size
gamma*n (previous algorithms were known only for gamma>1/2). 
This algorithm uses n^(1/poly(gamma)) levels of the Lasserre SDP hierarchy.