Xi Chen
| Naissance | |
|---|---|
| Nationalité | Américain |
| Domaines | informatique théorique, théorie algorithmique des jeux |
|---|---|
| Institutions | Institute for Advanced Study, Université de Princeton, Université Columbia |
| Formation | Université Tsinghua |
| Directeur de thèse | Bo Zhang |
| Renommé pour | complétude PPAD des équilibres de Nash |
| Distinctions | SIAM Outstanding Paper Prize (2016), prix Presburger (2015), Alfred P. Sloan Research Fellowship (2011) |
| Site | www.cs.columbia.edu/~xichen/Homepage/Welcome.html |
Xi Chen, né en 1982, est un 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
[modifier | modifier le code]Xi Chen fait ses études universitaires à l'université Tsinghua, avec une licence en physique et mathématiques en 2003 et un 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[1]. Il est ensuite, de 2007 à 2010, post-doc à l'Institute for Advanced Study à l'université de Princeton, à l'université du Sud de la Californie et enfin à l'Université Columbia[2]. Il est depuis janvier 2011 professeur associé au département d'informatique l'Université Columbia[3].
Recherche
[modifier | modifier le code]Xi Chen a apporté des contributions fondamentales dans divers domaines d'informatique théorique. Ses travaux en théorie algorithmique des jeux et en économie computationnelle comprennent notamment la réponse à une question restée longtemps ouverte sur la complexité du calcul des équilibres de Nash pour les jeux à deux joueurs, pour lesquels il démontre la complétude PPAD dans un travail commun avec Xiaotie Deng[4]. Il a également démontré la complétude PPAD pour diverses catégories de marchés et 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 #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 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 temps qui est exponentiel en .
Xi Chen travaille également sur les 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 fonctions booléennes telles que la monotonie et la propriété d'être une junte[5].
Publications (sélection)
[modifier | modifier le code]- [2013] Jin-Yi Cai, Xi Chen et Pinyan Lu, « Graph Homomorphisms with Complex Values: A Dichotomy Theorem », SIAM Journal on Computing, vol. 42, no 3, , p. 924–1029 (ISSN 0097-5397, DOI 10.1137/110840194).
- [2016] Jin-Yi Cai, Xi Chen et Pinyan Lu, « Nonnegative Weighted #CSP: An Effective Complexity Dichotomy », SIAM Journal on Computing, vol. 45, no 6, , p. 2177–2198 (ISSN 0097-5397, DOI 10.1137/15M1032314) — Version détaillé d'une communication à la IEEE Conference on Computational Complexity (2011)
- [2017] Xi Chen, Erik Waingarten et Jinyu Xie, « Beyond Talagrand functions: new lower bounds for testing monotonicity and unateness », STOC 2017 Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, , p. 523–536 (DOI 10.1145/3055399.3055461)
Prix et distinctions
[modifier | modifier le code]En 2006, le Best Paper Award lui est attribué au 47e IEEE Symposium on Foundations of Computer Science. En 2011, Xi Chen obtient un Alfred P. Sloan Research Fellowship. 201 En 2015, l'EATCS décerne le prix Presburger à Xi Chen[6] En 2016, il obtient un SIAM Outstanding Paper Prize pour l'article « How to Compress Interactive Communication » avec Boaz Barak, Mark Braverman et Anup Rao[7] 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
[modifier | modifier le code]- Page personnelle de Xi Chen.
- Curriculum Vitaæ.
- Xi Chen sur le Columbia Engineering Magazine
-
Xi Chen et Xiaotie Deng « Settling the complexity of two-player Nash equilibrium » () (DOI 10.1109/FOCS.2006.69)
—Proc. 47th Symp. Foundations of Computer Science. - Xi Chen, Rocco A. Servedio, Li-Yang Tan, Erik Waingarten et Jinyu Xie, « Settling the Query Complexity of Non-Adaptive Junta Testing », Computational Complexity Conference, , p. 26:1-26:19 (DOI 10.4230/LIPIcs.CCC.2017.26, lire en ligne).
- The EATCS bestows the Presburger Award 2015 on Xi Chen (Columbia University)
- Boaz Barak, Mark Braverman, Xi Chen et Anup Rao, « How to Compress Interactive Communication », SIAM Journal on Computing, vol. 42, no 3, , p. 1327–1363 (ISSN 0097-5397, DOI 10.1137/100811969).
Liens externes
[modifier | modifier le code]- Ressources relatives à la recherche :
- Publications de Xi Chen sur DBLP
- Theory highlights sur Columbia University
