Xi Chen

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.

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 Areas

• Economics & Computation
• Game Theory