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 two different angles:

• 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.

Lecture notes for the class.

Material covered in class:

1. 11 Nov 24: Introduction (Section 1).
2. 18 Nov 24: Gadget reductions (Section 2.1) and their connection to polymorphisms (Sections 2.4, 2.5).
3. 25 Nov 24: Galois connection (Section 2.5). Outline of proof of Schaefer’s theorem (Section 2.6).
4. 02 Dec 24: Reduction to linear equations (Section 2.6), 2SAT, (dual) HornSAT (Section 2.7). Proof of Schaefer’s theorem (Section 2.6). We briefly covered arc consistency (Section 2.2).
5. 09 Dec 24: Introduction to hardness of approximation (Sections 3.1, 3.2).
6. 16 Dec 24: Linearity testing by local correction (Section 3.3), Linearity testing using Fourier analysis (Section 3.4), Dictatorship testing and folding (Section 3.5).
7. 23 Dec 24: Hardness for MAX-3LIN (Section 3.6).
8. 13 Jan 24: Max-Cut: Algorithm (Section 4.1), tight instance (Section 4.2).
9. 20 Jan 24: Max-Cut: Integrality gap (Section 4.3), hardness of MAX-2LIN (Section 4.4).
10. 27 Jan 24: Max-Cut: Hardness of MAX-CUT (Section 4.4), Raghavendra’s theorem for MAX-CUT and O’Donnell–Wu (Section 4.5).
11. 17 Feb 24: Student presentations.

Assignments:

1. Assignment 1, posted 01 Dec 24, due 23 Dec 24. Solution.
2. Assignment 2, posted 23 Dec 24, due 13 Jan 25. Solution.