TIME: 1:30-2:20 pm,  February 5, 2008

PLACE: CSE 503  

SPEAKER: Alexandra Kolla
         U.C. Berkeley

TITLE: Unique Games on Expanding Constraint Graphs are Easy

ABSTRACT:
I will present efficient algorithms to find a good solution to the
Unique Games problem when the constraint graph is an expander. 
I will show two different ways of finding highly satisfying assignments
when they exist.  The first approach introduces a new analysis of the
vector solution for the standard SDP that involves correlations among
distant vertices.  The second approach is based on the observation that
the information of the satisfying labeling is encoded within the first
few eigenvectors of the label-extended graph.  This leads to a simple
spectral partitioning algorithm for recovering highly satisfying assignments.

This is joint work with Sanjeev Arora, Subash Khot, David Steurer, 
Madhur Tulsiani and Nisheeth Vishnoi.