Jin-Yi Cai (Chinese:蔡进一; born 1961) is a Chinese Americanmathematician andcomputer scientist. He is a professor of computer science, and also theSteenbock Professor of Mathematical Sciences[1] at theUniversity of Wisconsin–Madison. His research is intheoretical computer science, especiallycomputational complexity theory. In recent years he has concentrated on the classification of computationalcounting problems, especially countinggraph homomorphisms, countingconstraint satisfaction problems, and Holant problems as related toholographic algorithms.
Cai was born inShanghai, China. He studied mathematics atFudan University, graduating in 1981.He earned a master's degree atTemple University in 1983, a second master's degree atCornell University in 1985,[2] and his Ph.D. from Cornell in 1986, withJuris Hartmanis as hisdoctoral advisor.[3]
He became a faculty member atYale University (1986-1989),Princeton University (1989-1993), andSUNY Buffalo (1993-2000), rising fromAssistant Professor toFull Professor in 1996. He became a Professor of Computer Science at theUniversity of Wisconsin–Madison in 2000.[2]
Cai was aPresidential Young Investigator,Sloan Research Fellow,[4] and aGuggenheim Fellow.[5] He received aMorningside Silver Medal, and aHumboldt Research Award for Senior U.S. Scientists.[2] He was jointly awarded theGödel Prize in 2021, an award in theoretical computer science for his work in the paper titled:Complexity of Counting CSP with Complex Weights.[6] He was also awarded theFulkerson Prize in Discrete Mathematics awarded by the American Mathematical Society and the Mathematical Programming Society.[7]
He was elected a Fellow of theAssociation for Computing Machinery (2001),American Association for the Advancement of Science (2007), and a foreign member ofAcademia Europaea (2017).[2] He was named to the 2023 class of Fellows of theAmerican Mathematical Society, "for contributions to computational complexity theory, especially in the areas of complexity dichotomy".[8]
