# Xi Chen

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

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. 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. Il est depuis janvier 2011 professeur associé au département d'informatique l'Université Columbia.

## Recherche

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. 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 $n^{1/5}$.
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.

## Publications (sélection)

* [2013] Jin-Yi Cai, Xi Chen et Pinyan Lu, « Graph Homomorphisms with Complex Values: A Dichotomy Theorem », SIAM Journal on Computing, vol. 42, n$^o$ 3,‎ 2013, 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, n$^o$ 6,‎ 2016, 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,‎ 2017, p. 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 Alfred P. Sloan Research Fellowship. 201 En 2015, l'EATCS décerne le prix Presburger à Xi Chen 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 En 2021, il est lauréat du prix Fulkerson avec Jin-Yi Cai pour Complexity of Counting CSP with Complex Weights.