The optimization problem corresponding to a constraint satisfaction problem (CSP) consists of finding an assignment that satisfies as many constraints of the CSP instance as possible. For most CSPs, including many for which satisfiability can be decided in polynomial time, the associated optimization problem is NP-hard. To cope with this intractability, the approximate solvability of CSPs by polynomial time algorithms and limits on the performance guarantees of such algorithms have been extensively studied. For many problems we now have good approximation algorithms as well as strong (or even tight) complementary hardness results. This tutorial is an introduction to this subject, and we will discuss some of its central algorithmic and hardness results, leading up to its current frontiers.

On the algorithmic side, linear and semidefinite programming relaxations have been the most successful tool for designing good approximation algorithms for CSPs. We will discuss how to write canonical LP and SDP relaxations for CSPs, and see some examples of algorithms based on them and the non-trivial approximation ratios they are able to guarantee.

On the hardness side, we will review the PCP theorem and state some strong non-approximability results obtained by reductions from a CSP called Label Cover. These results prove that many natural CSPs are approximation resistant, in that outputting a random assignment yields essentially the best possible approximation guarantee. We will discuss the notion of Dictatorship testing and its utility in the context of proving non-approximability results via reductions from a special form of Label Cover called Unique Games. For illustration, we will discuss a tight dictator test for the Boolean CSP consisting of 3-variable linear equations.

We will then discuss recent progress based on the ``Unique Games conjecture'' which is able to identify the approximation threshold of every CSP as the integrality gap of a natural semidefinite programming relaxation, using the simplest binary CSP, MaxCut, for illustration. Time permitting, we may draw a parallel with the algebraic dichotomy conjecture, and comment how --- under the Unique Games conjecture --- the approximability of a CSP is precisely governed by the existence of non-trivial approximate polymorphisms.