Thursday, April 12, 2018
Moshe Y. Vardi, the Karen Ostrum George Distinguished Service Professor in Computational Engineering and director of the Ken Kennedy Institute for Information Technology at Rice University, will share with a colleague the 2018 Alonzo Church Award for Outstanding Contributions to Logic and Computation.
The award to Vardi and Tomás Feder of Stanford University is given in recognition of their “fundamental contributions to the computational complexity of constraint-satisfaction problems.” Eligible for the award are the authors of a paper or series of papers published within the past 25 years. Their research resulted in the formulation of the Feder-Vardi Dichotomy Conjecture, which culminated in 2017 in two independent proofs, by Andrei Bulatov and Dmitriy Zhuk.
The award was established in 2015 by the ACM Special Interest Group for Logic and Computation, the European Association for Theoretical Computer Science, the European Association for Computer Science Logic and the Kurt Gödel Society.
This year’s award is given for two papers written by Vardi and Feder: “Monotone Monadic SNP and Constraint Satisfaction,” delivered to the ACM Symposium on the Theory of Computing, 1993; and “The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory,” published in the SIAM Journal of Computing in 1998.
Vardi earned his Ph.D. in computer science from Hebrew University in Jerusalem in 1981. After two tenures as a research scientist for IBM Research and continued work at Stanford University, Vardi joined the Rice faculty in 1993. He is a member of the U.S. National Academy of Engineering, the National Academy of Sciences and the American Academy of Arts and Sciences.
The award will be presented during the 33rd ACM/IEEE Symposium on Logic in Computer Science to be held July 9-12 in Oxford, U.K.
Patrick Kurp, Engineering Communications