Voir la source de Xi Chen

{{Infobox Scientifique
 | nom               = Xi Chen
 | image             = Xi Chen computer scientist.jpg
 | légende           = 
 | upright           = 
 | nom de naissance  = 
 | date de naissance = 1982
 | lieu de naissance = 
 | date de décès     = 
 | lieu de décès     = 
 | nationalité       = Américain
 | pays de naissance = 
 | pays de décès     = 
 | actif             = <!-- date ou période d'activité connue (par exemple en l'absence de date de naissance connue) -->
 | domicile          = 
 | domaines          = [[informatique théorique]], [[théorie des jeux|théorie algorithmique des jeux ]]
 | institutions      = [[Institute for Advanced Study]], [[Université de Princeton]], [[Université Columbia]]
 | diplôme           = 
 | formation         = [[Université Tsinghua]]
 | directeur thèse   = Bo Zhang
 | étudiants thèse   = 
 | influencé par     = 
 | a influencé       = 
 | renommé pour      = complétude [[PPAD (complexité)|PPAD]] des [[équilibre de Nash|équilibres de Nash]]
 | prix              = ''SIAM Outstanding Paper Prize'' (2016), [[prix Presburger]] (2015), [[Bourse Sloan|Alfred P. Sloan Research Fellowship]] (2011)
 | notes             = 
 | signature         = 
 | site              = {{url|http://www.cs.columbia.edu/~xichen/Homepage/Welcome.html}}
}}'''Xi Chen''', né en 1982, est un [[informatique théorique|informaticien théoricien]] américain, professeur  au département d'informatique l'[[Université Columbia]]. Ses thèmes de recherche sont l'informatique théorique, y compris la théorie algorithmique des jeux et l'économie, la théorie de la complexité, le test d'isomorphisme de graphes et le test de propriétés.

== Biographie ==
Xi Chen fait ses études universitaires à l'[[université Tsinghua]], avec une licence en physique et mathématiques en 2003 et un [[Philosophiæ doctor|Ph. D.]]  en 2007 sous la direction de Bo Zhang. Il y était membre de l'institut d’informatique théorique dirigé par Andrew Chi-Chih Yao<ref>[http://www.cs.columbia.edu/~xichen/Homepage/Welcome.html Page personnelle] de Xi Chen.</ref>. Il est ensuite, de 2007 à 2010, [[Chercheur postdoctoral|post-doc]] à l'[[Institute for Advanced Study]] à l'[[université de Princeton]], à l'[[université du Sud de la Californie]] et enfin à l'[[Université Columbia]]<ref name="cv">[http://www.cs.columbia.edu/~xichen/Homepage/Welcome_files/CV_Full.pdf Curriculum Vitaæ].</ref>. Il est depuis janvier 2011 professeur associé au département d'informatique l'[[Université Columbia]]<ref>[https://magazine.engineering.columbia.edu/faculty/xichen Xi Chen] sur le ''Columbia Engineering Magazine''</ref>.

== Recherche ==

Xi Chen a apporté des contributions fondamentales dans divers domaines d'informatique théorique. Ses travaux en [[théorie des jeux|théorie algorithmique des jeux ]] et en [[économie computationnelle]] comprennent notamment la réponse à une question restée longtemps ouverte sur la [[Théorie de la complexité (informatique théorique)|complexité du calcul]] des [[équilibre de Nash|équilibres de Nash]] pour les jeux à deux joueurs, pour lesquels il démontre la complétude [[PPAD (complexité)|PPAD]] dans un travail commun avec Xiaotie Deng<ref>
{{lien conférence
|prénom1=Xi|nom1=Chen
|prénom2=Xiaotie|nom2=Deng
|titre=Settling the complexity of two-player Nash equilibrium
|conférence=Proc. 47th Symp. Foundations of Computer Science
|année=2006
|passage=261–271
|doi=10.1109/FOCS.2006.69|id={{ECCC|2005|05|140}}}}.
</ref>. Il a également démontré la complétude [[PPAD (complexité)|PPAD]] pour diverses catégories de marchés et  [[Utilité (économie)#Représentation mathématique de la fonction d'utilité|fonctions d'utilité]] largement utilisés en économie. 

En théorie de la complexité, Xi Chen démontre un théorème de dichotomie complète pour la complexité de certaines fonctions, montrant qu'elle est ou bien polynomiale ou bien 
[[Sharp-P-complet|#P-complete]] ; ceci comprend le calcul de fonctions de partition ainsi que des problèmes de satisfaction de contraintes avec des poids complexes, des concepts qui incluent par exemple le dénombrement des [[morphisme de graphes| homomorphismes de graphes]]. Ses contributions en algorithmique comprennent une preuve que l'isomorphisme de graphes fortement réguliers, un cas difficile du [[problème de l'isomorphisme de graphes]], peut être testé en un [[complexité en temps|temps]] qui est exponentiel en <math>n^{1/5}</math>.

Xi Chen travaille également sur les [[test de propriété|tests de propriétés]], un domaine qui étudie les algorithmes de temps sous-linéaire qui peuvent déterminer si un ensemble massif de données possède une certaine propriété ou est loin d'avoir cette propriété. Il établit de nouvelles bornes supérieures et inférieures pour les tests de propriétés des propriétés naturelles pour les [[Fonction booléenne|fonctions booléennes]] telles que la monotonie et la propriété d'être une junte<ref>
{{article
|auteur1= Xi Chen
|auteur2= Rocco A. Servedio
|auteur3= Li-Yang Tan
|auteur4= Erik Waingarten
|auteur5= Jinyu Xie
|titre = Settling the Query Complexity of Non-Adaptive Junta Testing
|journal = Computational Complexity Conference
|année= 2017
|pages = 26:1-26:19
|doi=10.4230/LIPIcs.CCC.2017.26
|url=https://drops.dagstuhl.de/opus/volltexte/2017/7528}}.</ref>.

== Publications (sélection) ==
* {{article|libellé=2013
|auteur1=[[Jin-Yi Cai]]
|nom2=Chen|prénom2=Xi|
nom3=Lu|prénom3=Pinyan
|titre=Graph Homomorphisms with Complex Values: A Dichotomy Theorem
|journal=SIAM Journal on Computing|volume=42|numéro=3|année=2013|pages=924–1029
|issn=0097-5397|doi=10.1137/110840194}}.
* {{article|libellé=2016
|nom1=Cai|prénom1=Jin-Yi
|nom2=Chen|prénom2=Xi
|nom3=Lu|prénom3=Pinyan
|titre=Nonnegative Weighted #CSP: An Effective Complexity Dichotomy
|journal=SIAM Journal on Computing|volume=45|numéro=6|année=2016|pages=2177–2198|issn=0097-5397|doi=10.1137/15M1032314}} — Version détaillé d'une communication à la IEEE Conference on Computational Complexity (2011)
* {{article|libellé=2017
|nom1=Chen|prénom1=Xi
|nom2=Waingarten|prénom2=Erik
|nom3=Xie|prénom3=Jinyu
|titre=Beyond Talagrand functions: new lower bounds for testing monotonicity and unateness
|journal = STOC 2017 Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing 
|année=2017|pages=523–536|doi=10.1145/3055399.3055461}}

== Prix et distinctions ==
En 2006, le ''Best Paper Award'' lui est attribué au {{47e}} IEEE Symposium on Foundations of Computer Science.
En 2011, Xi Chen obtient un [[Bourse Sloan|Alfred P. Sloan Research Fellowship]].
201
En 2015, l'[[European Association for Theoretical Computer Science|EATCS]] décerne le [[prix Presburger]] à Xi Chen<ref>[http://eatcs.org/index.php/component/content/article/1-news/2066-the-eatcs-bestows-the-presburger-award-2015-on-xi-chen-columbia-university The EATCS bestows the Presburger Award 2015 on Xi Chen (Columbia University)]</ref>
En 2016, il obtient un ''SIAM Outstanding Paper Prize'' pour l'article « How to Compress Interactive Communication » avec Boaz Barak, [[Mark Braverman (mathématicien)|Mark Braverman]] et Anup Rao<ref>{{article|nom1=Barak|prénom1=Boaz|nom2=Braverman|prénom2=Mark|nom3=Chen|prénom3=Xi|nom4=Rao|prénom4=Anup|titre=How to Compress Interactive Communication|journal=SIAM Journal on Computing|volume=42|numéro=3|année=2013|pages=1327–1363|issn=0097-5397|doi=10.1137/100811969}}.</ref>
En 2021, il est lauréat du [[prix Fulkerson]] avec Jin-Yi Cai pour ''Complexity of Counting CSP with Complex Weights''.

== Notes et références ==
{{Références}}

== Liens externes ==
{{Liens}}
* [https://dblp.uni-trier.de/pers/hd/c/Chen_0001:Xi Publications] de Xi Chen sur [[Digital Bibliography & Library Project|DBLP]]
* [https://theory.cs.washington.edu/news.html Theory highlights] sur Columbia University

{{Palette|Lauréats du prix Presburger|Lauréats du prix Gödel}}

{{Portail|informatique théorique}}

{{DEFAULTSORT:Chen, Xi}}
[[Catégorie:Personnalité en informatique théorique]]
[[Catégorie:Lauréat du prix Fulkerson]]
[[Catégorie:Étudiant de l'université Tsinghua]]