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.