Jin-Yi Cai
 | This article, Jin-Yi Cai, has recently been created via the Articles for creation process. Please check to see if the reviewer has accidentally left this template after accepting the draft and take appropriate action as necessary.
Reviewer tools: Inform author |
 |
Jin-Yi Cai (Chinese: 蔡进一; born 1961) is a Chinese American mathematician and computer scientist. He is a professor of computer science, and also the Steenbock Professor of Mathematical Sciences[1] at the University of Wisconsin-Madison. His research is in theoretical computer science, especially computational complexity theory. In recent years he has concentrated on the classification of computational counting problems, especially counting graph homomorphisms, counting constraint satisfaction problems, and Holant problems as related to holographic algorithms.
Early life
Cai was born in Shanghai, China. He attended Fudan University as a member of the class 77, where he studied mathematics.
After coming to the United States in 1981, he attended Temple University studying with Donald J. Newman, and then at Cornell University, where he received his Ph. D. in 1986 under Juris Hartmanis.
Academic career
He became a faculty member at Yale University (1986-1989), Princeton University (1989-1993), and SUNY Buffalo (1993-2000), rising from Assistant Professor to Full Professor in 1996. He became a Professor of Computer Science at the University of Wisconsin-Madison in 2000.
Key contributions
Cai's research results include:
- His proof that a random oracle separates the polynomial-time hierarchy from PSPACE with probability one.[2]
- The CFI-construction[3] (joint work with Martin Fürer and Neil Immerman).
- Complexity dichotomy theorems for the partition functions of graph homomorphisms, constraint satisfaction problems (CSP), and Holant problems.[4][5][6]
His book Complexity Dichotomies for Counting Problems: Volume 1. Boolean Domain coauthored with Xi Chen[7] ) was published by Cambridge University Press in 2018.[8]
Awards
Cai was a Presidential Young Investigator, Sloan Research Fellow[9] , and a Guggenheim Fellow[10]. He received a Morningside Silver Medal, and a Humboldt Research Award for Senior U.S. Scientists. He was elected a Fellow of the Association for Computing Machinery (2001), American Association for the Advancement of Science (2007), and a foreign member of Academia Europaea (2017). He was jointly awarded the Gödel Prize in 2021, an award in theoretical computer science for his work in the paper titled: Complexity of Counting CSP with Complex Weights.[11] He was also awarded the Fulkerson Prize in Discrete Mathematics awarded by the American Mathematical Society and the Mathemtical Programming Society. [12]
References
- ^ "Two faculty members named Steenbock Professors".
- ^ Cai, Jin-Yi (1989). "With probability one, a random oracle separates PSPACE from the polynomial-time hierarchy". Journal of Computer and System Sciences. 38: 68–85. doi:10.1016/0022-0000(89)90033-0.
- ^ Cai, Jin-Yi; f�Rer, Martin; Immerman, Neil (1992). "An optimal lower bound on the number of variables for graph identification". Combinatorica. 12 (4): 389–410. doi:10.1007/BF01305232. S2CID 30787182.
{{cite journal}}: replacement character in|last2=at position 2 (help) - ^ Cai, Jin-Yi; Chen, Xi; Lu, Pinyan (2013). "Graph Homomorphisms with Complex Values: A Dichotomy Theorem". SIAM Journal on Computing. 42 (3): 924–1029. arXiv:0903.4728. doi:10.1137/110840194.
- ^ Cai, Jin-Yi; Chen, Xi (2017). "Complexity of Counting CSP with Complex Weights". Journal of the ACM. 64 (3): 1–39. arXiv:1111.2384. doi:10.1145/2822891. S2CID 1053684.
- ^ Cai, Jin-Yi; Fu, Zhiguo (2019). "Holographic Algorithm with Matchgates is Universal for Planar #CSP over Boolean Domain". SIAM Journal on Computing: STOC17–50. arXiv:1603.07046. doi:10.1137/17M1131672.
- ^ "Xi Chen's Home page".
- ^ "Complexity Dichotomies for Counting Problems | Algorithmics, complexity, computer algebra and computational geometry".
- ^ "Past Fellows | Alfred P. Sloan Foundation".
- ^ "John Simon Guggenheim Foundation | Fellows".
- ^ https://sigact.org/prizes/gödel/citation2021.html
- ^ "Delbert Ray Fulkerson Prize (AMS-MOS)".