Worst-Case Approximation Ratios for Some Constraint Satisfaction Problems

In this talk, I will describe some recent progress on the worst-case approximation ratios for some Boolean constraint satisfaction problems. This includes determining the exact approximation ratios for MAX 2-SAT and its subproblems, separating MAX DI-CUT (maximum directed cut) from MAX CUT and MAX 2-AND, as well as proving that MAX NAE-SAT, where each constraint is satisfied if and only if its literals are not all equal, has an approximation ratio strictly less than 7/8. All these results assume the Unique Games Conjecture.