Computer Sciences Professor Jin-Yi Cai has been awarded the Fulkerson Prize for work in discrete mathematics. He received the award in recognition of his article “Complexity of Counting CSP with Complex Weights,” jointly with Xi Chen of Columbia University, which was published in the Journal of the ACM (Association for Computing Machinery) in 2017.
The Fulkerson Prize is awarded jointly by the American Mathematical Society and the Mathematical Optimization Society every three years. It was first awarded in 1979, and the first year winners included Karp for his NP-completeness work and Appel and Haken for solving the four color conjecture.
“I am tremendously honored by the Fulkerson Prize,” said Cai. “By recognizing our work in the complexity of counting problems, complexity theory is now widely accepted as an important branch of mathematical sciences.”
Cai is the Steenbock Professor of Mathematical Sciences at the University of Wisconsin. Recipients are nominated by a department or a group of three or more faculty members, and they are selected by an expert committee from American and Canadian universities.
Cai has been a professor in the Computer Sciences Department at UW-Madison since 2000 after previous academic positions at Yale, Princeton, and SUNY Buffalo. He earned a PhD from Cornell University in 1986, and his research is focused on computational complexity theory. Cai co-authored the book Complexity Dichotomies for Counting Problems: Volume 1, published by Cambridge University Press in 2018.