Tuesday, February 17, 2015

EATCS Fellows class of 2015 named

The EATCS has recognized five of its members for their outstanding contributions to theoretical computer science by naming them as recipients of an EATCS fellowship.

The EATCS Fellows for 2015 are:
  • Artur Czumaj (University of Warwick, United Kingdom) for "contributions to analysis and design of algorithms, especially to understanding the role of randomization in computer science";
  • Mariangiola Dezani-Ciancaglini (Universit√† di Torino, Italy) for "distinguished and seminal achievements in formal methods and foundations of programming languages, introducing or developing new type systems for the lambda-calculus as well as for the pi-calculus and related calculi";
  • Thomas A. Henzinger (Institute of Science and Technology Austria) for "fundamental contributions to formal verification and synthesis of computer and biological systems";
  • Dexter Kozen (Cornell University, USA) for "pioneering and seminal work in fields as diverse as  complexity theory, logics of programs, algebra, computer algebra and probabilistic semantics";
  • Moshe Y. Vardi (Rice University, USA) for "fundamental and lasting contributions to the development of logic in computer science and exceptional services to the community of theoretical computer science."
The aforementioned members of the EATCS were selected by the EATCS Fellow Selection Committee, after examining the nominations received from our research community. The EATCS Fellow Selection Committee for 2015 consisted of
  • Rocco De Nicola (IMT Lucca, Italy),
  • Paul Goldberg (Oxford, UK),
  • Anca Muscholl (Bordeaux, France),
  • Dorothea Wagner (Karlsruhe, Germany; chair) and
  • Roger Wattenhofer (ETH Zurich, CH).
The EATCS Fellows Program was established by the association  in 2014 to recognize outstanding EATCS members for their scientific achievements in the field of Theoretical Computer Science.

The EATCS is very proud to have the above-mentioned members of the organization among its fellows.

The list of EATCS Fellows is available at  http://www.eatcs.org/index.php/eatcs-fellows.

Monday, February 16, 2015

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


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).

Research Positions in Algorithms and Networks at Reykjavik University

Applications are invited for two research positions at the School of Computer Science (SCS), Reykjavik University, funded by a grant from the Icelandic Research Fund, under the direction of Prof. Magnus M. Halldorsson.  The positions can be either at any level: Ph.D. student, post-doctoral, or at faculty level. The application deadline is March 15, 2015.

The foci of the research group can be divided into three interrelated areas: algorithms for wireless networks; distributed graph algorithms; and approximation algorithms on graphs and networks.

Applicants should have a strong research profile (or potential) and a solid background in the analysis of algorithms. A general understanding of networking and/or distributed computing is expected. Self-motivation, open mind and team spirit are all helpful ingredients.

For more information and application procedures, see full announcement at
For informal inquires, contact Magnus M. Halldorsson, mmh@ru.is.

Thursday, February 12, 2015

Call for Nominations: EiC for ACM Transactions on Computational Logic

Call for Nominations
ACM Transactions on Computational Logic

The term of the current Editor-in-Chief (EiC) of the journal ACM Transactions on Computational Logic (TOCL) is coming to an end, and the ACM Publications Board has set up a nominating committee to assist the Board in selecting the next EiC. TOCL was established in 2000 and has been experiencing steady growth, with 74 submissions received in 2014.

Nominations, including self nominations, are invited for a three-year term as TOCL EiC, beginning on July 1, 2015. The EiC appointment may be renewed at most once. This is an entirely voluntary position, but ACM will provide appropriate administrative support.

For further details, see