Xi Chen (* um 1981) ist ein chinesisch-US-amerikanischer Informatiker.

Xi Chen studierte ab 1999 an der Universität Tsinghua mit dem Bachelor-Abschluss in Physik und Mathematik 2003 und der Promotion in Informatik 2007 bei Bo Zhang. Dort war er am Institut für theoretische Informatik bei Andrew Chi-Chih Yao. Als Post-Doktorand war er am Institute for Advanced Study (2007/08), an der Princeton University (2008/09), der University of Southern California (2009/10) und de der Columbia University (2010), an der er 2011 Assistant Professor und 2016 Associate Professor (mit tenure) wurde.

Xi-Chen befasst sich mit Komplexitätstheorie, algorithmischer Spieltheorie, Testen von Graph-Isomorphismen und Graph-Eigenschaften und Wirtschaftswissenschaften

Für 2021 wurde ihm gemeinsam mit Jin-Yi Cai 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 das 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 war Sloan Research Fellow (2012), erhielt einen Career Award der National Science Foundation und 2015 den Presburger Award der EATCS.

Er ist nicht mit dem Professor an der Stern School of Business der New York University Xi Chen zu verwechseln, zumal er sich auch mit theoretischen Wirtschaftswissenschaften befasst.

Schriften (Auswahl)

  • mit Jin-Yi Cai: Complexity Dichotomies for Counting Problems, Band 1: Boolean Domain, Cambridge UP 2017

Einzelnachweise

  1. ↑ Jin-Yi Cai, Xi Chen, Complexity of Counting CSP with Complex Weights, Journal of the ACM, Band 64, 2017, S. 1–39, Arxiv
  2. ↑ Gödel Prize 2021
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.