Presburger Award 2015 to Xi Chen (Columbia University)

The European Association for Theoretical Computer Science (EATCS) has awarded the 2015 Presburger Award to  Xi Chen (Columbia University, New York, USA). Congratulations to Chen!

Xi Chen, born in 1982, has made 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 polynomial 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 n^1/5 - the first significant progress in more than a decade.

The  Presburger Award is given to a young scientist (in exceptional cases to several young scientists)  for outstanding contributions in theoretical computer science, documented by a published paper or a series of published papers. The list of the previous recipients of the Presburger Award is available at

http://eatcs.org/index.php/presburger

The Presburger Award carries a prize money of 1000 Euros and will be delivered at ICALP 2015, which will take place in Kyoto (Japan) from the 6th till the 10th of July 2015 in co-location with LICS 2015.

The 2015 Presburger Award Committee consisted of Zoltan Esik (University of Szeged, Hungary), Claire Mathieu (ENS Paris, France) and Peter Widmayer (ETH Zurich, CH; chair).