Sangxia Huang: Approximability of Some Constraint Satisfaction Problems

Lunch is served at 12:00 noon (register at doodle.com/b38thtqsmbvaw4n3 by Thursday April 18 at 8 pm). The presentation starts at 12:10 pm and ends at 1 pm. Those of us who wish reconvene after a short break for ca two hours of more technical discussions.

Abstract

I will talk about approximability of Constraint Satisfaction Problems (CSPs). In particular, we focus on CSPs of "sparse" Boolean predicates. This is also related to other optimization problems, such as finding maximum independent set. For CSP instances that are almost satisfiable, Siu On Chan proved recently that there is a predicate on k variables with k+1 accepting assignments that is NP-hard to approximate better than (k+1)/2^k. The case of approximation on satisfiable instances is rather different. This is also an important question, and I will describe many recent developments, including my own work.

For the first part, I will give an overview of the state of the art and some techniques --- mainly reductions for showing hardness. In the second part, I will go over some proofs in Chan's paper and prove part of the main result.

The talk does not require prior experience in the PCP business.