Xi Chen

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é de Californie du Sud et enfin à l'Université Columbia[2]. Il est depuis janvier 2011 professeur associé au département d'informatique l'Université Columbia[3].

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 divers 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 ${\displaystyle 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[5].

• [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)

En 2006, le Best Paper Award lui est attribué au 47^e 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.

• Publications de Xi Chen sur DBLP
• Theory highlights sur Columbia University

• Portail de l'informatique théorique