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 Barak, Moses Charikar, and Bernard Chazelle. Everyone is invited to attend his talk. His abstract 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 problems. 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.