ACM SIGACT Announces 2021 Knuth And Gӧdel Prizes
Moshe Vardi Receives Donald E. Knuth Prize; Five Researchers Recognized with Gödel Prize
New York, NY, June 16, 2021 – The Association for Computing Machinery’s Special Interest Group on Algorithms and Computation Theory (ACM SIGACT) recently announced that Moshe Vardi of Rice University is the recipient of the 2021 Knuth Prize for outstanding contributions that apply mathematical logic to multiple fundamental areas of computer science. ACM SIGACT also announced that the 2021 Gödel Prize is awarded to five researchers: Andrei Bulatov, Simon Fraser University; Martin E. Dyer, University of Leeds; David Richerby, University of Essex; Jin-Yi Cai, University of Wisconsin, Madison; and Xi Chen, Columbia University, for their work on constraint satisfaction, a vital area of study within theoretical computer science.
Vardi Receives Donald E. Knuth Prize
Vardi’s work has greatly increased our understanding of myriad computational systems. It has also led to significant practical applications such as industrial hardware and software verification. The major themes of Vardi’s contributions are the use of automata theory and logics of programs to algorithmically prove correctness of system designs; the analysis of database issues – including query evaluation complexity, data updates, and others – using finite-model theory; characterizations of complexity classes such as P in terms of logical expressions; and the analysis of multi-agent systems such as distributed computation systems, via epistemic logic.
A few of the key areas in which Vardi has made wide-ranging contributions include:
Automata-theoretic verification of system design
The paper, “Reasoning about infinite computations,” Vardi and co-author P. Wolper transformed statements about the correctness of a system into equivalent statements about the behavior of a finite automaton that has infinite length input words or infinite input trees.
Database theory
In “The complexity of relational query languages,” analyzed the computational complexity of the two query languages of relational databases, relational calculus and relational algebra, as well as extensions of both languages.
Knowledge in distributed systems
In a series of papers, Vardi and co-authors developed a widely applicable theory about facts, known or unknown, to various agents in a shared environment. This issue is of fundamental importance for distributed computation, as well as diverse areas including economics and artificial intelligence. These ideas were presented in the book Reasoning About Knowledge, which was co-authored by Vardi, Joseph Halpern, Yoram Moses, and Ronald Fagin.
The Donald E. Knuth Prize for outstanding contributions to the foundations of computer science is awarded for major research accomplishments and contributions to the foundations of computer science over an extended period of time. The Prize is awarded annually by the ACM Special Interest Group on Algorithms and Computation Theory (SIGACT) and the IEEE Technical Committee on the Mathematical Foundations of Computing (TCMF).
Group Recognized with Gödel Prize for Work on Constraint Satisfaction
Bulatov, Dyer, Richerby, Cai and Chen are recognized with the Gödel Prize for making important advances to the understanding of constraint satisfaction. The researchers advanced their ideas in the following papers:
Andrei Bulatov: “The Complexity of the Counting Constraint Satisfaction Problem.” The Counting Constraint Satisfaction Problem (#CSP(H)) over a finite relational structure H can be expressed as follows: given a relational structure G over the same vocabulary, determine the number of homomorphisms from G to H. In this paper, Bulatov characterizes relational structures H for which (#CSP(H) can be solved in polynomial time and prove that for all other structures the problem is #P-complete.
Martin E. Dyer and David Richerby: “An Effective Dichotomy for the Counting Constraint Satisfaction Problem.” In a 2008 paper, Andrei Bulatov gave a dichotomy for the counting constraint satisfaction problem. Dyer and Richerby give an elementary proof of Bulatov’s dichotomy, based on succinct representations, which they call frames, of a class of highly structured relations, which they call strongly rectangular. They show that these are precisely the relations which are invariant under a Mal’tsev polymorphism.
Jin-Yi Cai and Xi Chen: “Complexity of Counting CSP with Complex Weights.” In this paper, Cai and Chen give a complexity dichotomy theorem for the counting constraint satisfaction problem with algebraic complex weights.
About Constraint Satisfaction
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.
The Knuth and Gödel Prize recipients will be formally recognized with the 2021 Gödel Prize at the ACM Symposium on the Theory of Computing (STOC), which be held online from June 21-25.
The Gödel Prize is named in honor of Kurt Gödel, who was born in Austria-Hungary (now the Czech Republic) in 1906. Gödel's work has had immense impact upon scientific and philosophical thinking in the 20th century. The award is presented annually by ACM’s Special Interest Group on Algorithms and Computation Theory (SIGACT) and the European Association for Theoretical Computer Science (EATCS).
About ACM SIGACT
The ACM Special Interest Group on Algorithms and Computation Theory fosters and promotes the discovery and dissemination of high quality research in the domain of theoretical computer science. The field includes algorithms, data structures, complexity theory, distributed computation, parallel computation, VLSI, machine learning, computational biology, computational geometry, information theory, cryptography, quantum computation, computational number theory and algebra, program semantics and verification, automata theory, and the study of randomness. Work in this field is often distinguished by its emphasis on mathematical technique and rigor.
About ACM
ACM, the Association for Computing Machinery, is the world's largest educational and scientific computing society, uniting educators, researchers, and professionals to inspire dialogue, share resources, and address the field's challenges. ACM strengthens the computing profession's collective voice through strong leadership, promotion of the highest standards, and recognition of technical excellence. ACM supports the professional growth of its members by providing opportunities for life-long learning, career development, and professional networking.
Contact:
Samir Khuller
ACM SIGACT Chair
847-491-2748
[email protected]
Jim Ormond
ACM
212-626-0505
[email protected]