Computer Sciences Professor Jin-Yi Cai has been awarded a WARF Named Professorship. The professorship honors “faculty who have made contributions to the advancement of knowledge” through their research, teaching, and service activities. Nine other UW-Madison faculty members received the award, a distinguishing feature of which is that recipients choose the name for their professorship.
Cai has chosen to name his professorship after Juris Hartmanis, a founding father of computational complexity theory. Hartmanis, together with Richard Stearns, wrote the seminal paper that established the field, for which they received the highest prize in computer science, the Turing Award. Hartmanis’s research contributions included defining complexity classes, time and space hierarchy theorems, isomorphisms among NP-complete sets, sparse sets, and the Boolean hierarchy. He founded the computer science department at Cornell University in 1965 establishing one of the world’s leading CS Departments. He also contributed tremendously to the national efforts to advance computational science and engineering (CS&E) in the US.
Cai studied mathematics at Fudan University in Shanghai, China, in the entering class of 1977. He received his PhD in computer science under Juris Hartmanis from Cornell University in 1986. After faculty positions at Yale (1986-1989), Princeton (1989-1993), and SUNY Buffalo (1993-2000), rising from Assistant Professor to Full Professor in 1996, he joined UW-Madison Computer Sciences in 2000. He was the Steenbock Professor of Mathematical Sciences 2014-2024, and became the Rajiv & Rita Batra Chair in Computer Science in 2024. His research focuses on computational complexity theory. His work aims to classify computational problems according to their inherent complexity. In recent years he concentrated on complexity dichotomy theorems for counting problems at the P versus NP level.
He was a Presidential Young Investigator in 1990, a Sloan Fellow in 1994, a Guggenheim Fellow in 1998. He was elected a Fellow of AAAS, ACM, AMS, and a foreign member of Academia Europaea. He received the Gödel Prize in Theoretical Computer Science and the Fulkerson Prize in Discrete Mathematics.
Congratulations, Professor Cai!