Xi Chen is 2015 Winner of the EATCS Presburger Award

Xi Chen was named this year’s recipient of the Presburger Award. Since 2010, the award has been bestowed by the European Association for Theoretical Computer Science (EATCS) to “a young scientist for outstanding contributions in theoretical computer science, documented by a published paper or a series of published papers.” The award is named after Mojzesz Presburger, who while still a student in 1929 invented the field of Presburger arithmetic, whose simplicity—it involves only addition of natural numbers—means Gödel’s Incompleteness Theorem does not apply to it.

Chen was selected for his fundamental contributions in a variety of areas within theoretical computer science. “His work in algorithmic game theory and computational economics includes the answer to the long-standing question about the computational complexity of Nash equilibria for two-player games, showing PPAD-completeness. For classes of markets and types of utility functions widely used in economics, he settled the complexity of market equilibria, again showing PPAD-completeness. His work on complexity theory includes a complete dichotomy theorem for partition function computation, showing it to be either polynomi- al or #P-complete, as well as for counting constraint satisfaction problems with complex weights, general concepts that include e.g. counting graph homomorphisms. His work on algorithms includes a proof that isomorphism of strongly regular graphs, a well-known hard case for the graph isomorphism problem, can be tested in time exponential in n1/5—the first significant progress in more than a decade.”

It is unusual for someone so young (Chen was born in 1982) to have already written papers that contributed to many different aspects of theoretical computer science.

“I feel honored to receive this award and be included in the company of the previous winners whose work I know and respect,” said Chen.

Chen joined the Columbia Computer Science Department in 2011. He attended Tsinghua University where he received a BS degree in Physics/Math (2003) and a PhD in Computer Science (2007).