Yury Makarychev will present his preFPO on Monday April 30 at 2:30PM in Room 402. The members of his committee are: Moses Charikar, advisor; Bernard Chazelle and Assaf Naor (NYU), readers; Boaz Barak and Rob Schapire, nonreaders. Everyone is invited to attend his talk. His abstract follows below. ================================================================== Title: Approximation Algorithms for Constraint Satisfaction Problems Constraint satisfaction problems (CSP) are very basic and natural combinatorial optimization problems. Given a set of variables and constraints on them, our goal is to satisfy as many constraints as possible. Our interest in constraint satisfaction problems is twofold. First of all, CSPs are good model problems. They are well suited for developing new algorithmic techniques, which can potentially be applied to other problems of interest. Another reason to study CSPs is their importance to complexity theory. Many problems arising in complexity theory such as 3SAT, Unique Games, and Label Cover (which is closely related to PCPs) are constraint satisfaction problems. I will describe approximation algorithms for two constraint satisfaction problems. First, I will talk about the Unique Games Problem. A unique game is a CSP with a "uniqueness" property: each constraint involves two variables and the value of one variable uniquely determines the value of the other. The Unique Games Problem generalizes such problems as MAX CUT and MAX-2-LIN (linear equations mod p with two variables per equation). This problem has recently attracted a lot of attention since hardness of approximation for many problems, such as Sparsest Cut and Vertex Cover, was proved assuming the Unique Games Conjecture. Roughly speaking, this conjecture says that even if almost all constraints in a unique game are satisfiable it is NP-hard to satisfy a small constant fraction of constraints. Unique games pose a great challenge for our existing techniques: Typically, semidefinite programming (SDP) relaxations are well suited for optimization problems involving boolean variables (e.g. MAX CUT). But little is known about how to analyze SDP solutions for problems with larger domains. I will describe several nearly optimal approximation algorithms for the Unique Games Problem. Then I will talk about the Maximum k-CSP problem. In this problem, each constraint is an arbitrary predicate on at most k variables. I will describe approximation algorithms for different ranges of parameters (k and the fraction of unsatisfied constraints in the optimal solution). The algorithms are almost optimal assuming the Unique Games Conjecture. ==================================================================