Xi Chen

ASSOCIATE PROFESSOR OF COMPUTER SCIENCE

503 S.W. Mudd
Mail Code 0401

Tel(212) 939-7136
Fax(212) 666-0140

Xi Chen specializes in algorithmic game theory and complexity theory. He is interested in understanding the power and limits of algorithms for fundamental computational problems of practical importance and theoretical interest. The goal of his research is to advance the knowledge of these problems by either designing new efficient algorithms or revealing their intrinsic hardness using complexity-theoretic tools.

Research Interests

Algorithmic game theory, complexity theory, sub-linear algorithms.

Chen has worked on the computational complexity of classic solution concepts from game theory and economics such as Nash equilibria and Arrow-Debreu market equilibria. His work on algorithmic mechanism design showed that the problem of finding a revenue-optimal mechanism (or auction) is intractable even under highly restricted settings. He has developed new techniques for the complexity classification of counting problems, where he obtained dichotomy theorems that completely classify the complexity of large families of counting problems based on unified tractability criteria. His work on graph isomorphism testing improved a decades-old best known upper bound for strongly regular graphs. Recently he has been working on property testing, an area that studies sublinear-time algorithms that can tell whether a massive dataset has a certain property or is far from having the property. His work has led to new upper and lower bounds for the property testing of natural properties for Boolean functions such as monotonicity and the property of being a junta.

Chen received his BS in physics/mathematics and PhD in computer science from Tsinghua University, in 2003 and 2007, respectively. Before joining SEAS in 2011, he was a postdoctoral researcher at the Institute for Advanced Study, Princeton University, and USC. He received an NSF CAREER Award, a Sloan research fellowship, and a Presburger Award by the European Association for Theoretical Computer Science.

 

RESEARCH EXPERIENCE

  • Postdoctoral researcher, Columbia University, 2010 – 2011
  • Postdoctoral researcher, University of Southern California, 2009 – 2010
  • Postdoctoral researcher, Princeton University, 2008 – 2009
  • Postdoctoral researcher, Institute for Advanced Study, 2007 – 2008

PROFESSIONAL EXPERIENCE

  • Associate professor, Computer Science, Columbia University, 2015 – now
  • Assistant professor, Computer Science, Columbia University, 2011 – 2015

HONORS & AWARDS

  • SIAM Outstanding Paper Award, 2016
  • EATCS Presburger Award, 2015
  • Alfred P. Sloan Research Fellowship, 2012
  • NSF CAREER Award, 2012       

GRANT SUPPORT

  • NSF CCF-1703925, Title: New Frontiers in Equilibrium Computation (Jointly with PI Mihalis Yannakakis), 2017 – 2021

SELECTED PUBLICATIONS

  • Xi Chen, Rocco A. Servedio, Li-Yang Tan, Erik Waingarten and Jinyu Xie, Settling the Query Complexity of Non-adaptive Junta Testing, In Proceedings of the 32nd Computational Complexity Conference (CCC), 2017.
  • Xi Chen, Erik Waingarten and Jinyu Xie, Beyond Talagrand Functions: New Lower Bounds for Testing Monotonicity and Unateness, In Proceedings of the 49th ACM Symposium on Theory of Computing (STOC), 2017.
  • Xi Chen, Igor C. Oliveira and Rocco A. Servedio, Addition is Exponentially Harder Than Counting for Shallow Monotone Circuits, In Proceedings of the 49th ACM Symposium on Theory of Computing (STOC), 2017.
  • Xi Chen, Igor C. Oliveira, Rocco A. Servedio and Li-Yang Tan, Near-Optimal Small-Depth Lower Bounds for Small Distance Connectivity, In Proceedings of the 48th ACM Symposium on Theory of Computing (STOC), 2016.
  • László Babai, Xi Chen, Xiaorui Sun, Shang-Hua Teng and John Wilmes, Faster Canonical Forms for Strongly Regular Graphs, In Proceedings of the 54th Annual Symposium on Foundations of Computer Science (FOCS), 2013.
  • Xi Chen, Dimitris Paparas and Mihalis Yannakakis, The Complexity of Non-Monotone Markets, In Proceedings of the 45th ACM Symposium on Theory of Computing (STOC), 2013.
  • Jin-Yi Cai, Xi Chen and Pinyan Lu, Graph Homomorphisms with Complex Values: A Dichotomy Theorem, SIAM Journal on Computing, 42(3), 924–1029, 2013.
  • Boaz Barak, Mark Braverman, Xi Chen and Anup Rao, How to Compress Interactive Communication, SIAM Journal on Computing 42(3): 1327-1363, 2013.
  • Jin-Yi Cai and Xi Chen, Complexity of Counting CSP with Complex Weights, In Proceedings of the 44th ACM Symposium on Theory of Computing (STOC), 2012.
  • Xi Chen, Xiaotie Deng and Shang-Hua Teng, Settling the Complexity of Computing Two-Player Nash Equilibria, Journal of the ACM, 56(3): 1–57, 2009.