Jin-Yi Cai: Difference between revisions

Content deleted Content added

Inline

Revision as of 17:55, 11 August 2021

Jin-Yi Cai (Chinese: 蔡进一; born January 23, 1961) is 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, studying 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 with probability one a random oracle separates the polynomial-time hierarchy from PSPACE.^[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 the Cambridge University Press in 2018.^[8]

Awards

Cai has been a Presidential Young Investigator, a Sloan Fellow, and a Guggenheim Fellow. 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, one of the most prestigious awards in theoretical computer science for his work in the paper titled: Complexity of Counting CSP with Complex Weights^[9] He was also awarded the Fulkerson Prize in Discrete Mathematics awarded by the American Mathematical Society and the Mathemtical Programming Society. ^[10]

References

[1] ttps://news.wisc.edu/two-faculty-members-named-steenbock-professors/

[2] ttps://www.sciencedirect.com/science/article/pii/0022000089900330

[3] ttps://link.springer.com/article/10.1007/BF01305232

[4] ttps://epubs.siam.org/doi/abs/10.1137/110840194?mobileUi=0&

[5] ttps://dl.acm.org/doi/abs/10.1145/2822891

[6] ttps://epubs.siam.org/doi/abs/10.1137/17M1131672?af=R

[7] ttp://www.cs.columbia.edu/~xichen/Homepage/Welcome.html

[8] ttps://www.cambridge.org/gb/academic/subjects/computer-science/algorithmics-complexity-computer-algebra-and-computational-g/complexity-dichotomies-counting-problems-volume-1?format=HB#DFBHvIwbXJQwt13s.97

[9] ttps://sigact.org/prizes/gödel/citation2021.html

[10] ttp://www.ams.org/prizes-awards/paview.cgi?parent_id=17

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

@@ Line 2: / Line 2: @@
 {{Bare|date=August 2021}}
-Jin-Yi Cai ([[Chinese language|Chinese]]: 蔡进一; born January 23, 1961) is Chinese American mathematician and [[Computer scientist|computer scientist]]. He is a professor of computer science, and also the [https://research.wisc.edu/professorships-and-faculty-fellowships/steenbock-professorships/ Steenbock Professor of Mathematical Sciences]<ref>https://news.wisc.edu/two-faculty-members-named-steenbock-professors/</ref> at the [[University of wisconsin-madison|University of Wisconsin-Madison]]. His research work focuses
+Jin-Yi Cai ([[Chinese language|Chinese]]: 蔡进一; born January 23, 1961) is Chinese American [[Mathematician|mathematician]] and [[Computer scientist|computer scientist]]. He is a professor of computer science, and also the [https://research.wisc.edu/professorships-and-faculty-fellowships/steenbock-professorships/ Steenbock Professor of Mathematical Sciences]<ref>https://news.wisc.edu/two-faculty-members-named-steenbock-professors/</ref> at the [[University of wisconsin-madison|University of Wisconsin-Madison]]. His research  is in [[Theoretical computer science|theoretical computer science]], especially [[Computational complexity theory|computational complexity theory]].   In recent years he has concentrated on the classification of computational counting problems, especially counting [[Graph homomorphism|graph homomorphisms]], counting [[Constraint satisfaction problem|constraint satisfaction problems]], and Holant problems as related to [[Holographic algorithm|holographic algorithms]].
-on [[Computational complexity theory|algorithmic complexity theory]] and [[Theoretical computer science|theoretical computer science]]. In recent years he has concentrated on the classification of computational counting problems, especially counting [[Graph homomorphism|graph homomorphisms]], counting constraint satisfaction problems, and Holant problems as related to [[Holographic algorithm|holographic algorithms]].
 == Early life ==
 Cai was born in [[Shanghai, China]]. He attended [[Fudan University]] as a
-member of the class 77, graduating with a degree in  ___________ TO DO PUT DEGREE HERE _____________
+member of the class 77, studying mathematics.
 After coming to the United States in 1981, he attended [[Temple University]]
 studying with [[Donald J. Newman]], and then at [[Cornell University]],
@@ Line 21: / Line 22: @@
 == Key contributions ==
 Cai's research results include:
-* His proof that with probability one a random oracle separates the polynomial-time hierarchy from PSPACE<ref>https://www.sciencedirect.com/science/article/pii/0022000089900330</ref>
+* His proof that with probability one a random oracle separates the polynomial-time hierarchy from PSPACE.<ref>https://www.sciencedirect.com/science/article/pii/0022000089900330</ref>
 *The CFI-construction<ref>https://link.springer.com/article/10.1007/BF01305232</ref> (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<ref>https://epubs.siam.org/doi/abs/10.1137/110840194?mobileUi=0&</ref><ref>https://dl.acm.org/doi/abs/10.1145/2822891</ref><ref>https://epubs.siam.org/doi/abs/10.1137/17M1131672?af=R</ref>
+*Complexity dichotomy theorems for the partition functions of graph homomorphisms, constraint satisfaction problems (CSP), and Holant problems.<ref>https://epubs.siam.org/doi/abs/10.1137/110840194?mobileUi=0&</ref><ref>https://dl.acm.org/doi/abs/10.1145/2822891</ref><ref>https://epubs.siam.org/doi/abs/10.1137/17M1131672?af=R</ref>
-His book ''Complexity Dichotomies for Counting Problems: Volume 1. Boolean Domain'' coauthored with Xi Chen) was published by the Cambridge University Press in 2018.<ref>https://www.cambridge.org/gb/academic/subjects/computer-science/algorithmics-complexity-computer-algebra-and-computational-g/complexity-dichotomies-counting-problems-volume-1?format=HB#DFBHvIwbXJQwt13s.97</ref>
+His book ''Complexity Dichotomies for Counting Problems: Volume 1. Boolean Domain'' coauthored with Xi Chen <ref>http://www.cs.columbia.edu/~xichen/Homepage/Welcome.html</ref> ) was published by the Cambridge University Press in 2018.<ref>https://www.cambridge.org/gb/academic/subjects/computer-science/algorithmics-complexity-computer-algebra-and-computational-g/complexity-dichotomies-counting-problems-volume-1?format=HB#DFBHvIwbXJQwt13s.97</ref>
 == Awards ==
-Cai has been a [[Presidential Young Investigator Award|Presidential Young Investigator]], [[Sloan Fellows|a Sloan Fellow]], and a [[Guggenheim Fellowship|Guggenheim Fellow]]. He received a [[Morningside Medal|Morningside Silver Medal]], 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).
+Cai has been a [[Presidential Young Investigator Award|Presidential Young Investigator]], [[Sloan Fellows|a Sloan Fellow]], and a [[Guggenheim Fellowship|Guggenheim Fellow]]. He received a [[Morningside Medal|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, one of the most prestigious awards in theoretical computer science for his work in the paper titled: ''Complexity of Counting CSP with Complex Weights''<ref>https://sigact.org/prizes/gödel/citation2021.html</ref>
+He was jointly awarded the [[Gödel Prize]] in 2021, one of the most prestigious awards in theoretical computer science for his work in the paper titled: ''Complexity of Counting CSP with Complex Weights''<ref>https://sigact.org/prizes/gödel/citation2021.html</ref> He was also awarded the [[Fulkerson Prize]] in Discrete Mathematics awarded by the American Mathematical Society and the Mathemtical Programming Society. <ref>http://www.ams.org/prizes-awards/paview.cgi?parent_id=17</ref>
 == References ==