www.wikidata.de-de.nina.az

Jin Yi Cai 1961 ist ein chinesisch US amerikanischer Informatiker Cai studierte ab 1977 an der Fudan Universität Zertifi

Jin-Yi Cai

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). 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 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) von Leslie G. Valiant weiter.

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

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.

Schriften (Auswahl) Bearbeiten

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 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

Weblinks Bearbeiten

Einzelnachweise Bearbeiten

  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
Personendaten
NAME Cai, Jin-Yi
KURZBESCHREIBUNG chinesisch-US-amerikanischer Informatiker
GEBURTSDATUM 1961
wikipedia, wiki, deutsches, deutschland, buch, bücher, bibliothek artikel lesen, herunterladen kostenlos kostenloser herunterladen, MP3, Video, MP4, 3GP, JPG, JPEG, GIF, PNG, Bild, Musik, Lied, Film, Buch, Spiel, Spiele
Veröffentlichungsdatum:
Jin Yi Cai 1961 ist ein chinesisch US amerikanischer Informatiker Cai studierte ab 1977 an der Fudan Universitat 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 fur Mathematik ist 1995 bis 2001 und 2003 bis 2006 war er Gastprofessor an der Universitat Fudan in Shanghai 2010 bis 2013 Gastprofessor an der Universitat Peking und 2007 08 Radcliffe Fellow am Radcliffe Institute der Harvard University Cai befasst sich mit Komplexitatstheorie und Algorithmentheorie Fur 2021 wurde ihm gemeinsam mit Xi Chen ein Godel Preis zugesprochen fur ihre Arbeit An Effective Dichotomy for the Counting Constraint Satisfaction Problem von 2010 2 3 Wie die anderen Empfanger des Godel Preises von 2021 wurden damit Arbeiten gewurdigt die den Hohepunkt der Klassifikation von Abzahlkomplexitat von Constraint Satisfaction Problems CSP darstellen Sie bewiesen zusammen ein umfassendes Komplexitats Dichotomie Theorem fur CSP artige Abzahlprobleme die als Verteilungsfunktion partition function ausdruckbar sind alle diese Probleme sind entweder in Polynomzeit losbar oder Sharp P schwer Laudatio zum Godel Preis Fur 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 Anderungen 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 fur die Losung langer offener Probleme von Juris Hartmanis uber dunnbesetzte Mengen sparse sets und Beitrage zur Komplexitatstheorie 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 auswartiges Mitglied der Academia Europaea Er erhielt einen Humboldt Forschungspreis Schriften Auswahl BearbeitenAusser die in den Fussnoten erwahnten 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 Furer 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 1 1 dim e displaystyle 1 frac 1 text dim varepsilon nbsp is NP hard under randomized conditions Proc 33th Annual IEEE Conf Computational Complexity 1998 SVP ist das Problem des kurzesten 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 2017Weblinks BearbeitenWebseite an der University of Wisconsin mit CV Google ScholarEinzelnachweise Bearbeiten Jin Yi Cai im Mathematics Genealogy Project englisch Vorlage MathGenealogyProject Wartung id verwendet Jin Yi Cai Xi Chen Complexity of Counting CSP with Complex Weights Journal of the ACM Band 64 2017 S 1 39 Arxiv Godel Prize 2021 Brian Hayes Accidental Algorithms American Scientist Band 96 Januar Februar 2008 S 9 13 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 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 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 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 539Normdaten Person GND 17201378X lobid OGND AKS LCCN n90603435 VIAF 85610385 Wikipedia Personensuche PersonendatenNAME Cai Jin YiKURZBESCHREIBUNG chinesisch US amerikanischer InformatikerGEBURTSDATUM 1961 Abgerufen von https de wikipedia org w index php title Jin Yi Cai amp oldid 238166796