Note: this reading guide hasn't been significantly updated since 2019 - many recent results are missing from it. I'm still actively working on my notes on CSPs, which overlaps with the first half of the material in this reading guide quite a bit.

Here is a reading guide to the literature on the dichotomy conjecture for constraint satisfaction problems, and related stuff:

Start with this paper of Jeavons which explains the role of polymorphisms in puzzle solving. Take a brief look at the original paper of Feder and Vardi which introduces the dichotomy conjecture, and section 6 of this early paper which gives a procedure for computing the polymorphisms of a given arity by solving a particular instance of the CSP.

Read this paper by Dechter which introduces strong consistency. Follow it up with this paper by Baker and Pixley to see why near-unanimity operations guarantee strong consistency.

Next is this paper of Bulatov and Dalmau showing that any algebra having a Mal'tsev operation is tractable (in particular, this applies to quasigroups).

Optionally, read this paper of Bulatov and Jeavons which shows that one should really be studying varieties, and states the precise dichotomy conjecture (this paper cites a lot of previous results, but they have all been generalized in papers I will mention later). A good (optional) follow up paper is this paper of Barto on reflections, which clarifies the trick that lets you restrict to idempotent algebras.

This is probably a good time to skim this survey article by Carbonnel and Cooper. Optionally, if you like algebra and have a month to kill, read "The Structure of Finite Algebras" by Hobbie and McKenzie, "The Relationship Between Two Commutators" by Kearnes and Szendrei, and "Commutator Theory for Congruence Modular Varieties" by Freese and McKenzie.

Now we start playing for keeps.

The few subpowers algorithm. Start with this article by a ton of people, and follow it up with this one. As a crazy application, check out this paper, which shows that algebras with few subpowers are inherently finitely related. If you like clone theory, check out this paper on parallelogram terms.

For an introduction to absorption theory (and a preview of the results proved below), there is a nice survey by Barto and Kozik. (For additional spoilers, check out this collection of survey articles: Dagstuhl Follow-Ups, Vol. 7.)

Here's a three-in-one: this paper by Barto and Kozik proves the Absorption Theorem, the Loop Lemma/Smooth Theorem, and the existence of cyclic terms. A nice follow up is this paper by Kearnes, Markovic, and McKenzie (exercise: prove the existence of a term satisfying the identity t(x,x,y,z) = t(y,z,z,x) directly from the existence of a cyclic term).

Bounded width algebras. Start with this paper of Barto and Kozik, then read this one by Barto, Kozik, and Stanovsky, and finish it off with this paper by Barto. (For some background on how the ability to count is connected to congruence meet semidistributivity, check out this and maybe this.)

Cycle consistency. Marcin Kozik showed that bounded width problems can also be solved by the "cycle consistency" algorithm (and even by the weaker "pq consistency" algorithm): see here (the proof uses Theorem 6 from here, but this can be replaced by the simpler Lemma 3.5 from this paper).

Combining algorithms. This manuscript by Maroti describes how to solve problems in a variety generated by algebras with few subpowers and algebras of bounded width, while this one (also by Maroti) describes an ingenious way to combine a semilattice algebra with a tractable algebra. This paper of Bergman and Failing, based on Failing's thesis, has some nice results about Plonka sums of tractable algebras.

Bulatov's claimed solution to the CSP Dichotomy Conjecture (I haven't had time to check it yet). The argument is based on certain colored graphs associated to Taylor algebras: the main results about these colored graphs are proved in this paper. Apparently the main new idea in the proof shows up in this paper on "semilattice block Mal'tsev" algebras. The full proof is here.

Key relations and a second proof of the CSP Dichotomy Conjecture: a new approach to classifying relational clones by classifying "key relations" is outlined in this paper by Zhuk (for the Rosenberg Completeness Theorem, see this). For the dichotomy conjecture, check out this arxiv posting (earlier versions of this approach are outlined in these slides and these slides). A simplified proof of the algebraic core can be found here.

Finitely related algebras and the Valeriote conjecture. As a warmup, this paper by Barto shows that every finitely related congruence distributive algebra has near-unanimity terms. For background on congruence modularity, I recommend Gumm's book "Geometrical Methods in Congruence Modular Algebras", which has a very pretty way of visualizing the algebraic arguments. This paper by Barto proves the Valeriote conjecture: every finitely related congruence modular algebra has few subpowers (it relies on the existence of directed Gumm terms, which is proved here).

The Meta Problem. Whether there exists a polynomial time procedure to check if a given set of relations is preserved by an idempotent Siggers operation is currently open. In the conservative case, Carbonnel's thesis gives a polynomial time algorithm. In the case of non-core structures (and non-idempotent conditions), an NP-hardness result is proved in this paper by Chen and Larose.

Correlation Decay. An interesting analytic approach to understanding why cyclic operations imply tractability is described at a high level in this paper by Raghavendra and Brown-Cohen. For the full proof of their correlation decay result, see here (it may help with the background to first read Analysis of Boolean Functions by Ryan O'Donnell).

Time to branch out!

Treewidth. Using the Excluded Grid Theorem as a black box, this paper by Martin Grohe shows that structural tractability comes from bounded treewidth. (The Excluded Grid Theorem is rather difficult. If you want to give it a shot, this has a short proof of the treewidth duality theorem, this proves that there is a large grid-like-minor, Reed's chapter of this book gives a more in-depth introduction, and this recent paper of Julia Chuzhoy gives the best known bounds on the size of the grid minor.) Also check out this paper by Marx.

Robust solvability. This paper proves that a constraint language has symmetric polymorphisms of all arities if and only if it is solved by the canonical linear relaxation (it claims to show that this is equivalent to having width 1, but this paper gives a counterexample - as far as I can tell, the problem is that in general a fundamental group may be noncommutative), while this paper by Barto and Kozik proves that a constraint language has bounded width if and only if it is solved by the canonical semidefinite relaxation.

Valued CSPs. For finite valued constraints, read this and this by Thapper and Zivny. For general valued constraints, this sets up the theory of weighted clones and proves a Galois correspondence, this proves the general hardness result, and this reduces the dichotomy conjecture for VCSPs to the conjecture for CSPs. (This result about the power of the Sherali-Adams hierarchy is also nice.)

PCP and the Unique Games Conjecture. For the PCP theorem, Dinur's proof is quite direct (it relies on this variance bound, and some expander graph results). For shorter PCPs, combine Dinur's argument with this paper by Ben-Sasson and Sudan (this relies on a beautiful algebraic construction based on the de Bruijn router from this paper by Polishchuk and Spielman - for the properties of the de Bruijn router, the standard reference is chapter 3 of this textbook by Leighton). For inapproximability results, read this article by Hastad. For the Unique Games Conjecture, see this paper of Khot, Kindler, Mossel, and O'Donnell. For the optimal approximation algorithm (assuming UGC), see Raghavendra's thesis.

Counting complexity and the Holant framework. For #CSP, check out this. For weighted #CSP, see this. For Holant stuff, maybe this book by Jin-Yi Cai and Xi Chen.

Infinite algebras. The right framework for the infinite CSP seems to be oligomorphic algebras - check out Bodirsky's habilitation thesis. (For group theoretic background, check out this survey on oligomorphic groups by Peter Cameron, this paper on highly set-transitive groups, and this paper on reducts of the random hypergraph. For the Ramsey theory, this paper on extremely amenable groups has the main result, but you'll need to know about the partite method.) For a statement of the algebraic dichotomy conjecture for oligomorphic cores and a proof of the hardness result, see this paper of Barto and Pinsker, which generalizes a result of Bulatov on the H-coloring problem from the finite case to the infinite case. A method for reducing infinite domain CSPs to finite ones is outlined in this paper. See also this paper for a classification in a case which is not oligomorphic. For idempotent algebras, a nice result of Olsak shows that you don't need any finiteness assumptions to prove the existence of a "weak 3-cube term" satisfying t(x,y,y,y,x,x) = t(y,x,y,x,y,x) = t(y,y,x,x,x,y) in a Taylor variety.

Quantified constraints. The QCSP isn't understood well yet, but for some flavor we can start with this result on 2-semilattices. Hubie Chen gave a reasonable conjecture in this paper connecting the complexity of the QCSP to the "Polynomially Generated Powers" property (PGP for short). Zhuk proved that every algebra either has polynomially generated powers or exponentially generated powers in a very short paper, and Barnaby Martin points out that this settles a form of the dichotomy for idempotent algebras here. Some more difficult work on the QCSP for semicomplete digraphs can be found here. A classification of QCSP complexity in the idempotent case for domains of size 3, which refutes the Chen conjecture, can be found here (this paper also has a number of other surprising results). And now there is a really strong result: every QCSP is either PSPACE-hard or is contained in Pi₂, see here.

Promise CSPs. In this paper, Guruswami and Brakensiek show that the complexity of promise CSPs are controlled by what they call weak polymorphisms, but have trouble dealing with what they see as a lack of structure on the set of weak polymorphisms. The situation was clarified in this paper by Barto, Bulin, Krokhin, and Oprsal, which shows that the complexity of a PCSP is determined by the set of height 1 identities satisfied by their polymorphisms (the adjective weak is dropped), and the theory is applied to show that it is NP-complete to 5-color a graph which is promised to be 3-colorable.

Partial polymorphisms. This paper uses strong partial clones to find the easiest NP-complete case of SAT. This paper by Lagerkvist and Wahlstrom studies kernelizability of CSPs using partial polymorphisms. This paper by Lagerkvist and Wahlstrom studies the relationship between partial polymorphisms described by patterns and algorithms for NP-hard CSPs that outperform brute force. This paper by Carbonnel connects partial polymorphisms defined by patterns to nonredundancy of constraints in CSPs. Also, this describes a possible framework for proving circuit complexity bounds using partial polymorphisms.

Miscellaneous results. Generalizing algorithms based on Hall's Marriage Theorem and Dilworth's Theorem, we have the perfect graph theorem, and for perfect graphs the Lovasz theta number lets you compute the independence number efficiently. Generalizing Edmonds' Blossom Algorithm, we have this algorithm for "even delta-matroids", giving a partial dichotomy for Boolean edge CSPs (edge CSPs, introduced in this paper by Feder, are CSPs where each variable appears in only two constraints), and completing the classification of planar Boolean CSPs started here.

If you have any suggestions for a better way to rearrange this reading list, or an easier paper to replace one of these, send me an email!