Courses

A constraint satisfaction problem consists of a collection of variables and constraints. Each variable has an associated domain. The corresponding problem asks whether there is an assignment to the variables that satisfies all constraints; though this is not the only interesting problem which one can ask about a CSP instance. Two standard examples are SAT and $k$-coloring. Related problems are MAX-SAT and MAX-CUT, in which the goal is to maximize the number of satisfied constraints.

In this class, we will study CSPs from several angles (only some of the topics will be covered):

• Dichotomy theorems: SAT is NP-hard. What happens if we limit the type of constraints one is allowed to use? We will prove Schaefer’s dichotomy theorem, which states that if the variables are Boolean, then each type of CSP is either in P or NP-complete.
• Hardness of approximation: Consider a set of linear equations over $\mathit{GF}(2)$. A random assignment satisfies half of them, and in particular gives a $1/2$ approximation to the problem of maximizing the number of satisfied constraints. Can this be improved? We will prove Håstad’s result, showing that it is NP-hard to improve over this trivial algorithm. We will also show that the Goemans–Williamson algorithm is tight for MAX-CUT, assuming the unique games conjecture.
• How easy is it to refute a given CNF? We will consider Resolution, the proof system behind SAT solvers. We will prove exponential lower bounds on Resolution refutations of Tseitin contradictions on expanders, and (possibly) on refutations of random 3CNFs with the appropriate density, following classical work of Ben-Sasson and Wigderson.

Time-permitting, we will also briefly consider several other topics: exponential time algorithms for $k$SAT; certifying the unsatisfiability of random $k$CNFs; and the isolation lemma, with applications to approximate counting and sampling.

Lecture notes for the class.

Material covered in class:

1. 11 Nov 24: Introduction (Section 1).
2. 18 Nov 24: Gadget reductions and their connection to polymorphisms (Sections 2.1, 2.4, 2.5).
3. 25 Nov 24 (plan): Algorithms (Sections 2.2, 2.3); Galois connection (Section 2.5).
4. 02 Dec 24 (plan): Proof of Schaefer’s theorem (Section 2.6).