The Gödel Prize 2021

The Gödel Prize for outstanding papers in the area of theoretical computer science is sponsored jointly by the EATCS and the ACM SIGACT. The Prize is named in honor of Kurt Gödel in recognition of his major contributions to mathematical logic and of his interest, discovered in a letter he wrote to John von Neumann shortly before Neumann's death, in what has become the famous "P versus NP" question. The Prize includes an award of $5000 (US). This award is presented annually, with the presentation taking place alternately at the International Colloquium on Automata, Languages, and Programming (ICALP) and ACM Symposium on the Theory of Computing (STOC); it will be presented at STOC this year.

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)