Jin-Yi Cai (

Chinese Chinese can refer to: * Something related to China * Chinese people, people of Chinese nationality, citizenship, and/or ethnicity **''Zhonghua minzu'', the supra-ethnic concept of the Chinese nation ** List of ethnic groups in China, people of va ...

: 蔡进一; born 1961) is a Chinese American

mathematician A mathematician is someone who uses an extensive knowledge of mathematics in their work, typically to solve mathematical problems. Mathematicians are concerned with numbers, data, quantity, structure, space, models, and change. History On ...

and

computer scientist A computer scientist is a person who is trained in the academic study of computer science. Computer scientists typically work on the theoretical side of computation, as opposed to the hardware side on which computer engineers mainly focus (al ...

. He is a professor of computer science, and also th
Steenbock Professor of Mathematical Sciences
at the

University of Wisconsin–Madison A university () is an educational institution, institution of higher education, higher (or Tertiary education, tertiary) education and research which awards academic degrees in several Discipline (academia), academic disciplines. Universities ty ...

. His research is in

theoretical computer science Theoretical computer science (TCS) is a subset of general computer science and mathematics that focuses on mathematical aspects of computer science such as the theory of computation, lambda calculus, and type theory. It is difficult to circumsc ...

, especially

computational complexity theory In theoretical computer science and mathematics, computational complexity theory focuses on classifying computational problems according to their resource usage, and relating these classes to each other. A computational problem is a task solved by ...

. In recent years he has concentrated on the classification of computational counting problems, especially counting

graph homomorphism In the mathematical field of graph theory, a graph homomorphism is a mapping between two graphs that respects their structure. More concretely, it is a function between the vertex sets of two graphs that maps adjacent vertices to adjacent verti ...

s, counting

constraint satisfaction problem Constraint satisfaction problems (CSPs) are mathematical questions defined as a set of objects whose state must satisfy a number of constraints or limitations. CSPs represent the entities in a problem as a homogeneous collection of finite constra ...

s, and Holant problems as related to

holographic algorithm In computer science, a holographic algorithm is an algorithm that uses a holographic reduction. A holographic reduction is a constant-time reduction that maps solution fragments many-to-many such that the sum of the solution fragments remains un ...

Early life

Cai was born in

Shanghai, China Shanghai (; , , Standard Mandarin pronunciation: ) is one of the four direct-administered municipalities of the People's Republic of China (PRC). The city is located on the southern estuary of the Yangtze River, with the Huangpu River flowin ...

. He studied mathematics at

Fudan University Fudan University () is a national public research university in Shanghai, China. Fudan is a member of the C9 League, Project 985, Project 211, and the Double First Class University identified by the Ministry of Education of China. It is als ...

, graduating in 1981. He earned a master's degree at

Temple University Temple University (Temple or TU) is a public state-related research university in Philadelphia, Pennsylvania. It was founded in 1884 by the Baptist minister Russell Conwell and his congregation Grace Baptist Church of Philadelphia then called Ba ...

in 1983, a second master's degree at

Cornell University Cornell University is a private statutory land-grant research university based in Ithaca, New York. It is a member of the Ivy League. Founded in 1865 by Ezra Cornell and Andrew Dickson White, Cornell was founded with the intention to teach an ...

in 1985, and his Ph.D. from Cornell in 1986, with

Juris Hartmanis Juris Hartmanis (July 5, 1928 – July 29, 2022) was a Latvian-born American computer scientist and computational theorist who, with Richard E. Stearns, received the 1993 ACM Turing Award "in recognition of their seminal paper which established ...

as his

doctoral advisor A doctoral advisor (also dissertation director, dissertation advisor; or doctoral supervisor) is a member of a university faculty whose role is to guide graduate students who are candidates for a doctorate, helping them select coursework, as well ...

Academic career

He became a faculty member at

Yale University Yale University is a private research university in New Haven, Connecticut. Established in 1701 as the Collegiate School, it is the third-oldest institution of higher education in the United States and among the most prestigious in the wo ...

(1986-1989),

Princeton University Princeton University is a private university, private research university in Princeton, New Jersey. Founded in 1746 in Elizabeth, New Jersey, Elizabeth as the College of New Jersey, Princeton is the List of Colonial Colleges, fourth-oldest ins ...

(1989-1993), and

SUNY Buffalo The State University of New York at Buffalo, commonly called the University at Buffalo (UB) and sometimes called SUNY Buffalo, is a public research university with campuses in Buffalo and Amherst, New York. The university was founded in 1846 ...

(1993-2000), rising from

Assistant Professor Assistant Professor is an academic rank just below the rank of an associate professor used in universities or colleges, mainly in the United States and Canada. Overview This position is generally taken after earning a doctoral degree and general ...

Full Professor Professor (commonly abbreviated as Prof.) is an academic rank at universities and other post-secondary education and research institutions in most countries. Literally, ''professor'' derives from Latin as a "person who professes". Professors ...

in 1996. He became a Professor of Computer Science at the

in 2000.

Awards

Cai was a Presidential Young Investigator,

Sloan Research Fellow The Sloan Research Fellowships are awarded annually by the Alfred P. Sloan Foundation since 1955 to "provide support and recognition to early-career scientists and scholars". This program is one of the oldest of its kind in the United States. ...

, and a

Guggenheim Fellow Guggenheim Fellowships are grants that have been awarded annually since by the John Simon Guggenheim Memorial Foundation to those "who have demonstrated exceptional capacity for productive scholarship or exceptional creative ability in the ar ...

. He received a Morningside Silver Medal, and a

Humboldt Research Award The Humboldt Prize, the Humboldt-Forschungspreis in German, also known as the Humboldt Research Award, is an award given by the Alexander von Humboldt Foundation of Germany to internationally renowned scientists and scholars who work outside of G ...

for Senior U.S. Scientists. He was jointly awarded the

Gödel Prize The Gödel Prize is an annual prize for outstanding papers in the area of theoretical computer science, given jointly by the European Association for Theoretical Computer Science (EATCS) and the Association for Computing Machinery Special Inter ...

in 2021, an award in theoretical computer science for his work in the paper titled: ''Complexity of Counting CSP with Complex Weights.'' He was also awarded the

Fulkerson Prize The Fulkerson Prize for outstanding papers in the area of discrete mathematics is sponsored jointly by the Mathematical Optimization Society (MOS) and the American Mathematical Society (AMS). Up to three awards of $1,500 each are presented at e ...

in Discrete Mathematics awarded by the American Mathematical Society and the Mathemtical Programming Society. He was elected a Fellow of the

Association for Computing Machinery The Association for Computing Machinery (ACM) is a US-based international learned society for computing. It was founded in 1947 and is the world's largest scientific and educational computing society. The ACM is a non-profit professional member ...

(2001),

American Association for the Advancement of Science The American Association for the Advancement of Science (AAAS) is an American international non-profit organization with the stated goals of promoting cooperation among scientists, defending scientific freedom, encouraging scientific respons ...

(2007), and a foreign member of

Academia Europaea The Academia Europaea is a pan-European Academy of Humanities, Letters, Law, and Sciences. The Academia was founded in 1988 as a functioning Europe-wide Academy that encompasses all fields of scholarly inquiry. It acts as co-ordinator of Europea ...

(2017). He was named to the 2023 class of Fellows of the

American Mathematical Society The American Mathematical Society (AMS) is an association of professional mathematicians dedicated to the interests of mathematical research and scholarship, and serves the national and international community through its publications, meetings, ...

, "for contributions to computational complexity theory, especially in the areas of complexity dichotomy".

References

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