[talks] Y Makarychev preFPO

[Melissa M Lawson]

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.

==================================================================