Jin-Yi Cai – Wikipedia

Jin-Yi Cai (* 1961) ist ein chinesisch-US-amerikanischer Informatiker.

Cai studierte ab 1977 an der Fudan-Universität (Zertifikat in Mathematik 1981), an der Temple University mit dem Master-Abschluss (M.A.) 1983 und an der Cornell University, an der er 1985 einen Master-Abschluss (M.S.) erhielt und 1986 bei Juris Hartmanis an der Cornell University in Informatik promovierte (On Some Most Probable Separations of Complexity Classes).^[1] 1986 wurde er Assistant Professor an der Yale University und 1989 an der Princeton University, 1993 Associate Professor und 1996 Professor an der State University of New York at Buffalo und 2003 Professor an der University of Wisconsin-Madison., an der er seit 2014 Steenbock-Professor für Mathematik ist.

1995 bis 2001 und 2003 bis 2006 war er Gastprofessor an der Universität Fudan in Shanghai, 2010 bis 2013 Gastprofessor an der Universität Peking und 2007/08 Radcliffe Fellow am Radcliffe Institute der Harvard University.

Cai befasst sich mit Komplexitätstheorie und Algorithmentheorie.

Für 2021 wurde ihm gemeinsam mit Xi Chen ein Gödel-Preis zugesprochen für ihre Arbeit An Effective Dichotomy for the Counting Constraint Satisfaction Problem von 2010.^[2][3] Wie die anderen Empfänger des Gödel-Preises von 2021 wurden damit Arbeiten gewürdigt, die den Höhepunkt der Klassifikation von Abzählkomplexität von Constraint Satisfaction Problems (CSP) darstellen. Sie bewiesen zusammen ein umfassendes Komplexitäts-Dichotomie-Theorem für CSP-artige Abzählprobleme, die als Verteilungsfunktion (partition function) ausdrückbar sind: alle diese Probleme sind entweder in Polynomzeit lösbar oder Sharp-P-schwer (Laudatio zum Gödel-Preis). Für dieselbe Arbeit erhielten beide 2021 den Fulkerson-Preis.

Er entwickelte die holographischen Algorithmen (auch accidental algorithms)^[4] von Leslie G. Valiant weiter.^[5][6][7]

Cai entwickelte mit anderen einen effizienten Algorithmus um Änderungen in XML Dokumenten festzustellen (X-Diff).^[8]

1990 erhielt er einen Presidential Young Investigator Award der National Science Foundation, 1994 war er Sloan Research Fellow, 1998 Guggenheim Fellow und 2004 erhielt er die Morning Side Silver Medal in Mathematik für die Lösung langer offener Probleme von Juris Hartmanis über dünnbesetzte Mengen (sparse sets) und Beiträge zur Komplexitätstheorie (Laudatio).

Er ist Herausgeber beim Journal of Computer and Systems Sciences (JCSS), beim Chicago Journal of Theoretical Computer Science, im Herausgebergremium von Computational Complexity und Associate Editor des Journal of Complexity. Cai ist Fellow der Association for Computing Machinery (ACM), des IEEE, der American Association for the Advancement of Science und auswärtiges Mitglied der Academia Europaea. Er erhielt einen Humboldt-Forschungspreis.

Außer die in den Fußnoten erwähnten Arbeiten.

• mit T. F. Coleman: The cyclic coloring problem and estimation of sparse Hessian matrices, SIAM Journal on Algebraic Discrete Methods, Band 7, 1986, S. 221–235
• mit L. A. Hemachandra: The Boolean hierarchy: hardware over NP, in: Structure in Complexity Theory, 1986, S. 105–124
• mit T. Gundermann, J. Hartmanis, L. A. Hemachandra, V. Sewelson, K. Wagner, G. Wechsung: The boolean hierarchy I: Structural properties, SIAM Journal on Computing, Band 17, 1988, S. 1232–1252, Teil 2: Applications, Band 18, 1989, S. 95–111
• With probability one, a random oracle separates PSPACE from the polynomial-time hierarchy, Journal of Computer and System Sciences, Band 38, 1989, S. 68–85
• mit L. A. Hemachandra: Enumerative counting is hard, Information and Computation, Band 82, 1989, S. 34–44
• mit L. A. Hemachandra: On the power of parity polynomial time, Mathematical Systems Theory, Band 23, 1990, S. 95–106
• mit M. Fürer, N. Immerman: An optimal lower bound on the number of variables for graph identification, Combinatorica, Band 12, 1992, S. 389–410
• mit A. Nerukar: Approximating the SVP to within a factor ${\displaystyle (1-{\frac {1}{{\text{dim}}^{\varepsilon }}})}$ is NP-hard under randomized conditions, Proc. 33th Annual IEEE Conf. Computational Complexity, 1998 (SVP ist das Problem des kürzesten Gittervektors)
• mit V. Kabanets: Circuit minimization problem, Proc. 32. Annual Symp. on Theory of Computing (STOC), 2000
• mit Xi Chen: Complexity Dichotomies for Counting Problems, Band 1: Boolean Domain, Cambridge UP 2017

• Webseite an der University of Wisconsin mit CV
• Google Scholar

1. ↑ Jin-Yi Cai im Mathematics Genealogy Project (englisch) Vorlage:MathGenealogyProject/Wartung/id verwendet
2. ↑ Jin-Yi Cai, Xi Chen, Complexity of Counting CSP with Complex Weights, Journal of the ACM, Band 64, 2017, S. 1–39, Arxiv
3. ↑ Gödel Prize 2021
4. ↑ Brian Hayes, Accidental Algorithms, American Scientist, Band 96, Januar/Februar 2008, S. 9–13
5. ↑ Cai, Jin-Yi, Vinay Choudhary, Pinyan Lu, On the theory of matchgate computations, In Proceedings of the 22nd IEEE Conference on Computational Complexity, 2007, S. 305–318
6. ↑ Cai, Jin-Yi, Pinyan Lu, Holographic algorithms: From art to science. Proceedings of the 39th ACM Symposium on the Theory of Computing, STOC ’07, 2007, S. 401–410.
7. ↑ Cai, Jin-Yi, Pinyan Lu. Holographic algorithms: The power of dimensionality resolved, Proceedings of the 34th International Colloquium on Automata, Languages and Programming, ICALP 2007, S. 631–642.
8. ↑ Yuan Wang, David J. DeWitt, J.-Y. Cai, X-Diff: An effective change detection algorithm for XML documents, Proceedings 19th International Conference on Data Engineering, IEEE 2013, S. 519–539