Professor Jin-Yi Cai of the Department of Computer Sciences at the University of Wisconsin-Madison has been jointly awarded the prestigious Gödel Prize in theoretical computer science. The award is sponsored by the European Association for Theoretical Computer Science and the Association for Computing Machinery (ACM) Special Interest Group on Algorithms and Computation Theory (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 von Neumann’s death, in what has become the famous “P versus NP” question.
Cai’s award winning paper, “Complexity of Counting CSP with Complex Weights,” was written jointly with Xi Chen of Columbia University. Their paper gave a most general form of complexity classification to all counting constraint satisfaction problems specified by sets of complex-valued constraint functions. Counting CSP problems are ubiquitous in computer science and in other sciences including statistical physics. Their paper proved that every single problem in this broad class, expressed as a so-called partition function, is either computable in polynomial-time or equivalent to the hardest problem in the complexity class #P, the counting version of NP defined by Leslie Valiant.
Cai said he was very pleasantly surprised to win the Gödel Prize this year. “I am tremendously honored, and also humbled, by this prize named after Gödel.” He said it is also a fitting tribute to this department as Stephen C. Kleene and J. Barkley Rosser, two founding members of the Computer Sciences Department, played important roles in establishing the theory initiated by Gödel, Church, and Turing at the dawn of the computing era. He said, “Rosser improved Gödel’s Incompleteness Theorem by replacing ω-consistency by now the standard consistency condition, and Kleene’s work established the equivalence of all three approaches to computable functions by Gödel, Church, Turing, thus firmly establishing the Church-Turing thesis.”
Jin-Yi Cai is Professor of Computer Sciences and Steenbock Professor of Mathematical Sciences at UW-Madison. He received his PhD from Cornell University in 1986. After faculty positions at Yale, Princeton, and SUNY Buffalo, he joined UW-Madison in 2000. His previous honors include a Presidential Young Investigator Award in 1990, a Sloan Fellowship in 1994, a Guggenheim Fellowship in 1998, and a Morningside Silver Medal of Mathematics in 2004. He also received the Humboldt Research Award for Senior U.S. Scientists. He was elected a Fellow of ACM in 2001, a Fellow of AAAS in 2007, and a foreign member of Academia Europaea in 2017. His main research area is computational complexity theory.