Jump to content

Jin-Yi Cai: Difference between revisions

From Wikipedia, the free encyclopedia
Browse history interactively
← Previous edit
Content deleted Content added
VisualWikitext
Marking submission as under review (AFCH 0.9.1)
 
(19 intermediate revisions by 9 users not shown)
Line 1: Line 1:
{{Short description|Chinese-American computer scientist}}
{{AFC submission|r||u=Uwmadisoncdis|ns=118|reviewer=Danre98|reviewts=20210902212020|ts=20210819180727}} <!-- Do not remove this line! -->


⚫
'''Jin-Yi Cai''' ({{zh|s=蔡进一}}; born 1961) is a Chinese American [[mathematician]] and [[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>{{Cite web|url=https://news.wisc.edu/two-faculty-members-named-steenbock-professors/|title=Two faculty members named Steenbock Professors|website=news.wisc.edu}}</ref> 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 problem (complexity)|counting problems]], especially counting [[graph homomorphism]]s, counting [[constraint satisfaction problem]]s, and Holant problems as related to [[holographic algorithm]]s.
{{Bare|date=August 2021}}
⚫
Jin-Yi Cai ([[Chinese language|Chinese]]: 蔡进一; born 1961) is a 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>{{Cite web|url=https://news.wisc.edu/two-faculty-members-named-steenbock-professors/|title=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 problem (complexity)|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]].


== Early life ==
== Early life ==
Cai was born in [[Shanghai, China]]. He attended [[Fudan University]] as a
Cai was born in [[Shanghai, China]]. He studied mathematics at [[Fudan University]], graduating in 1981.
He earned a master's degree at [[Temple University]] in 1983, a second master's degree at [[Cornell University]] in 1985,<ref name=cv/> and his Ph.D. from Cornell in 1986, with [[Juris Hartmanis]] as his [[doctoral advisor]].<ref>{{mathgenealogy|id=79379}}</ref>
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 [[Doctor of Philosophy|Ph. D.]] in 1986 under [[Juris Hartmanis]].


== Academic career ==
== Academic career ==
Line 16: Line 11:
[[Princeton University]] (1989-1993), and [[SUNY-Buffalo|SUNY Buffalo]] (1993-2000),
[[Princeton University]] (1989-1993), and [[SUNY-Buffalo|SUNY Buffalo]] (1993-2000),
rising from [[Assistant professor|Assistant Professor]] to [[Full Professor]] in 1996.
rising from [[Assistant professor|Assistant Professor]] to [[Full Professor]] in 1996.
He became a Professor of Computer Science at the [[University of wisconsin-madison|University of Wisconsin-Madison]] in 2000.
He became a Professor of Computer Science at the [[University of Wisconsin–Madison]] in 2000.<ref name=cv>{{cite web|url=http://pages.cs.wisc.edu/~jyc/cv.pdf|title=Curriculum vitae|access-date=2021-09-12}}</ref>


== Key contributions ==
== Awards ==
Cai was a [[Presidential Young Investigator Award|Presidential Young Investigator]], [[Sloan Research Fellowship|Sloan Research Fellow]],<ref>{{Cite web|url=https://sloan.org/past-fellows|title=Past Fellows &#124; Alfred P. Sloan Foundation|website=sloan.org|access-date=2021-08-19|archive-date=2018-03-14|archive-url=https://web.archive.org/web/20180314000756/https://sloan.org/past-fellows|url-status=dead}}</ref> and a [[Guggenheim Fellowship|Guggenheim Fellow]].<ref>{{Cite web|url=https://www.gf.org/fellows/|title=John Simon Guggenheim Foundation &#124; Fellows|access-date=2021-08-19|archive-date=2021-02-14|archive-url=https://web.archive.org/web/20210214171150/https://www.gf.org/fellows/|url-status=dead}}</ref> He received a [[Morningside Medal|Morningside Silver Medal]], and a [[Humboldt Research Award]] for Senior U.S. Scientists.<ref name=cv/> 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.''<ref>{{Cite web|url=https://sigact.org/prizes/g%C3%B6del/citation2021.html|title=The 2021 Gödel Prize|website=sigact.org}}</ref> He was also awarded the [[Fulkerson Prize]] in Discrete Mathematics awarded by the American Mathematical Society and the Mathemtical Programming Society.<ref>{{Cite web|url=http://www.ams.org/prizes-awards/paview.cgi?parent_id=17|title = Delbert Ray Fulkerson Prize (AMS-MOS)}}</ref>
Cai's research results include:
* His proof that a random oracle separates the polynomial-time hierarchy from PSPACE with probability one.<ref>{{Cite journal|url=https://dx.doi.org/10.1016/0022-0000%2889%2990033-0|doi=10.1016/0022-0000(89)90033-0|title=With probability one, a random oracle separates PSPACE from the polynomial-time hierarchy|year=1989|last1=Cai|first1=Jin-Yi|journal=Journal of Computer and System Sciences|volume=38|pages=68–85}}</ref>
*The CFI-construction<ref>{{Cite journal|url=https://link.springer.com/article/10.1007/BF01305232|doi = 10.1007/BF01305232|title = An optimal lower bound on the number of variables for graph identification|year = 1992|last1 = Cai|first1 = Jin-Yi|last2 = f�Rer|first2 = Martin|last3 = Immerman|first3 = Neil|journal = Combinatorica|volume = 12|issue = 4|pages = 389–410|s2cid = 30787182}}</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>{{Cite journal|url=https://epubs.siam.org/doi/abs/10.1137/110840194?mobileUi=0&|doi=10.1137/110840194|title=Graph Homomorphisms with Complex Values: A Dichotomy Theorem|year=2013|last1=Cai|first1=Jin-Yi|last2=Chen|first2=Xi|last3=Lu|first3=Pinyan|journal=SIAM Journal on Computing|volume=42|issue=3|pages=924–1029|arxiv=0903.4728}}</ref><ref>{{Cite journal|url=https://dl.acm.org/doi/abs/10.1145/2822891|doi=10.1145/2822891|title=Complexity of Counting CSP with Complex Weights|year=2017|last1=Cai|first1=Jin-Yi|last2=Chen|first2=Xi|journal=Journal of the ACM|volume=64|issue=3|pages=1–39|arxiv=1111.2384|s2cid=1053684}}</ref><ref>{{Cite journal|url=https://epubs.siam.org/doi/abs/10.1137/17M1131672?af=R|doi=10.1137/17M1131672|title=Holographic Algorithm with Matchgates is Universal for Planar #CSP over Boolean Domain|year=2019|last1=Cai|first1=Jin-Yi|last2=Fu|first2=Zhiguo|journal=SIAM Journal on Computing|pages=STOC17–50|arxiv=1603.07046}}</ref>


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).<ref name=cv/> He was named to the 2023 class of Fellows of the [[American Mathematical Society]], "for contributions to computational complexity theory, especially in the areas of complexity dichotomy".<ref>{{cite web|url=http://www.ams.org/cgi-bin/fellows/fellows_by_year.cgi|title=2023 Class of Fellows|publisher=American Mathematical Society|access-date=2022-11-09}}</ref>
His book ''Complexity Dichotomies for Counting Problems: Volume 1. Boolean Domain'' coauthored with Xi Chen<ref>{{Cite web|url=http://www.cs.columbia.edu/~xichen/Homepage/Welcome.html|title = Xi Chen's Home page}}</ref> ) was published by Cambridge University Press in 2018.<ref>{{Cite web|url=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|title=Complexity Dichotomies for Counting Problems &#124; Algorithmics, complexity, computer algebra and computational geometry}}</ref>

== Awards ==
Cai was a [[Presidential Young Investigator Award|Presidential Young Investigator]], [[Sloan Research Fellowship|Sloan Research Fellow]]<ref>{{Cite web|url=https://sloan.org/past-fellows|title=Past Fellows &#124; Alfred P. Sloan Foundation}}</ref> , and a [[Guggenheim Fellowship|Guggenheim Fellow]]<ref>{{Cite web|url=https://www.gf.org/fellows/|title=John Simon Guggenheim Foundation &#124; Fellows}}</ref>. 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, an award 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>{{Cite web|url=http://www.ams.org/prizes-awards/paview.cgi?parent_id=17|title = Delbert Ray Fulkerson Prize (AMS-MOS)}}</ref>


== References ==
== References ==
<!-- Inline citations added to your article will automatically display here. See en.wikipedia.org/wiki/WP:REFB for instructions on how to add citations. -->
{{reflist}}
{{reflist}}


{{Gödel Prize laureates}}
<!-- categories go here -->
{{Authority control}}

{{DEFAULTSORT:Cai, Jin-Yi}}
[[Category:1961 births]]
[[Category:Living people]]
[[Category:Mathematicians from Shanghai]]
[[Category:American computer scientists]]
[[Category:Chinese computer scientists]]
[[Category:Theoretical computer scientists]]
[[Category:Fudan University alumni]]
[[Category:Temple University alumni]]
[[Category:Cornell University alumni]]
[[Category:Yale University faculty]]
[[Category:Princeton University faculty]]
[[Category:University at Buffalo faculty]]
[[Category:University of Wisconsin–Madison faculty]]
[[Category:2001 fellows of the Association for Computing Machinery]]
[[Category:Fellows of the American Mathematical Society]]
[[Category:Fellows of the American Association for the Advancement of Science]]
[[Category:Members of Academia Europaea]]

Latest revision as of 07:20, 13 September 2024

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

[edit]

Cai was born in Shanghai, China. He studied mathematics at Fudan University, graduating in 1981. He earned a master's degree at Temple University in 1983, a second master's degree at Cornell University in 1985,[2] and his Ph.D. from Cornell in 1986, with Juris Hartmanis as his doctoral advisor.[3]

Academic career

[edit]

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.[2]

Awards

[edit]

Cai was a Presidential Young Investigator, Sloan Research Fellow,[4] and a Guggenheim Fellow.[5] He received a Morningside Silver Medal, and a Humboldt Research Award for Senior U.S. Scientists.[2] 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.[6] He was also awarded the Fulkerson Prize in Discrete Mathematics awarded by the American Mathematical Society and the Mathemtical Programming Society.[7]

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).[2] He was named to the 2023 class of Fellows of the American Mathematical Society, "for contributions to computational complexity theory, especially in the areas of complexity dichotomy".[8]

References

[edit]
  1. ^ "Two faculty members named Steenbock Professors". news.wisc.edu.
  2. ^ a b c d "Curriculum vitae" (PDF). Retrieved 2021-09-12.
  3. ^ Jin-Yi Cai at the Mathematics Genealogy Project
  4. ^ "Past Fellows | Alfred P. Sloan Foundation". sloan.org. Archived from the original on 2018-03-14. Retrieved 2021-08-19.
  5. ^ "John Simon Guggenheim Foundation | Fellows". Archived from the original on 2021-02-14. Retrieved 2021-08-19.
  6. ^ "The 2021 Gödel Prize". sigact.org.
  7. ^ "Delbert Ray Fulkerson Prize (AMS-MOS)".
  8. ^ "2023 Class of Fellows". American Mathematical Society. Retrieved 2022-11-09.
Retrieved from "https://en.wikipedia.org/w/index.php?title=Jin-Yi_Cai&oldid=1245482635"