[talks] D Steurer preFPO

Melissa Lawson mml at CS.Princeton.EDU
Wed Feb 24 09:17:36 EST 2010

David Steurer will present his preFPO on Monday March 1 at 3PM in Room 402.  The 
members of his committee are:  Sanjeev Arora, advisor; Russell Impagliazzo (IAS), Boaz
Moses Charikar, and Bernard Chazelle.  Everyone is invited to attend his talk.  His
follows below.

On Strengths and Limits of Relaxations for Combinatorial Optimization

Mathematical programming relaxations are powerful tools for solving or
approximating combinatorial optimization problems. This thesis
explores the strengths and limits of these tools for a selection of
basic optimization problems.

A central open question in this context is the Unique Games Conjecture
(Khot 2002), which asserts that a certain optimization problem, called
Unique Games, is hard to approximate in a certain regime. In recent
years, a sequence of works established that this conjecture has
profound implications: If the conjecture is true, then a certain
semidefinite relaxations, called Basic-SDP, is optimal for a large
range of optimization problems, in the sense that no efficient
relaxation can achieve a better approximation for any of these

We make the following contributions towards a better understanding of
the Unique Games Conjecture and semidefinite relaxations of
combinatorial optimization problems:

- We exhibit an optimal rounding scheme for constraint satisfaction
  problems (CSPs), a well-studied class of combinatorial optimization
  problem. The guarantee of the scheme matches the integrality gap of
  the Basic-SDP relaxation for every CSP. In contrast to many previous
  rounding algorithms, our scheme is generic and very simple.
  Moreover, it allows for a principled analysis.

- Using our rounding scheme and a framework (Arora and Kale 2007) for
  solving semidefinite relaxations, we develop an approximation
  algorithm for CSPs whose approximation guarantee matches the
  integrality of the Basic-SDP relaxation and whose running time is
  quasi-linear. Assuming the Unique Games Conjecture, no polynomial
  time algorithm can have a better approximation guarantee.

- We confirm the Unique Games Conjecture for a restricted model of
  computation given by a hierarchy of semidefinite relaxations. In
  particular, we show that for every CSP, the integrality gap of the
  Basic-SDP cannot be improved by adding a large class of valid
  inequalities. It was a long-standing open question whether such
  stronger relaxation could lead to better approximation algorithms
  for problems like Max-Cut or Multiway-Cut. Our result answers this
  question in the negative.

- Finally, we establish a connection between the Unique Games
  Conjecture and the problem of approximating the expansion profile of
  graphs. In particular, we show that the Unique Games Conjecture is
  true if the expansion of small sets in graphs is hard to approximate
  in a certain regime. This result provides the first non-trivial
  sufficient condition for the truth of the conjecture. (Previously,
  only implications of the truth of the conjecture were known.)

Based on joint works with Prasad Raghavendra.

More information about the talks mailing list