The 2021 Gödel Prize is jointly awarded to the following three papers:

• Andrei Bulatov: The Complexity of the Counting Constraint Satisfaction Problem. J. ACM 60(5): 34:1–34:41 (2013).
• Martin E. Dyer and David Richerby: An Effective Dichotomy for the Counting Constraint Satisfaction Problem. SIAM J. Computing. 42(3): 1245–1274 (2013).
• Jin-Yi Cai and Xi Chen: Complexity of Counting CSP with Complex Weights. J. ACM 64(3): 19:1–19:39 (2017).

Constraint satisfaction is a subject of central significance in computer science, since a very large number of combinatorial problems, starting from Boolean Satisfiability and Graph Coloring, can be phrased as constraint satisfaction problems (CSP). The papers above, taken together, are the culmination of a large body of work on the classification of counting complexity of CSPs and prove an all-encompassing Complexity Dichotomy Theorem for counting CSP-type problems that are expressible as a partition function.

The class of problems that the final form of this dichotomy classifies is exceedingly broad. It includes all counting CSPs, all types of graph homomorphisms (undirected or directed, unweighted or weighted), and spin systems (and thus a large variety of problems from statistical physics). Examples include counting vertex covers, independent sets, antichains, graph colorings, the Ising model, the Potts model, the q-particle Widom-Rowlinson model, the q-type Beach model, and more. For all these problems this theorem gives a complexity dichotomy classification: Every problem in the class is either solvable in polynomial time or is #P-hard.

Award Committee:

Samson Abramsky (University of Oxford)
Nikhil Bansal (CWI Amsterdam)
Robert Krauthgamer (Weizmann Institute)
Ronitt Rubinfeld (Massachusetts Institute of Technology)
Daniel Spielman, Chair (Yale University)
David Zuckerman (University of Texas at Austin)