Tuesday, March 03, 2015

February 2015 issue of the Bulletin of the EATCS on line

Thanks to the work of Kazuo Iwama, editor in chief of the bulletin, and of his collaborators, the February 2015 issue of the Bulletin of the EATCS is now available on line. You can download the whole issue in PDF from here, if you prefer. As a service to the TCS community, the bulletin continues being open access because of the support of the members of the EATCS, whom I thank wholeheartedly.

Amongst other things, this issue contains contributions by David Eppstein on K-Best Enumeration, Vikraman Arvind on Robust Oracle Machines revisited, Gaudi Taubenfeld on A Closer Look at Concurrent Data Structures and Algorithms (pages 59-82 of the whole issue), Jukka Suomela on Local Coordination and Symmetry Breaking ((pages 83-110 of the whole issue), Andreas Blass on Negative Probability and by Juraj Hromkovic who kicks off the new-look Education Column with a piece entitled Homo Informaticus.

I welcome Stefan Schmid as new editor of the Distributed Computing Column and thank Panagiota Fatourou for her sterling editorial work over many years.

Enjoy it. 

Monday, March 02, 2015

Video made by the female CS student association at Reykjavik University

I learnt a few things about some of the students taking the first-year course I am teaching right now by watching this well-made video.

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


Tuesday, January 27, 2015

EATCS Award 2015 to Christos Papadimitriou

I am pleased to announce that the EATCS Awards Committee consisting of Fedor Fomin, Kim G. Larsen and Vladimiro Sassone (chair) has selected  Christos Papadimitriou (UC Berkeley, USA; WWW: http://www.cs.berkeley.edu/~christos/; Wikipedia: http://en.wikipedia.org/wiki/Christos_Papadimitriou) as the recipient of the EATCS Award 2015. Congratulations to Christos!

The award, which is given to acknowledge extensive and widely recognized contributions to theoretical computer science over a life long scientific career, will be presented to Christos at ICALP 2015, which will be held in Kyoto, Japan, in the period 6-10 July 2015. The list of previous recipients of the EATCS Award is here. An official laudatio for the award is forthcoming. What follows is a short preliminary laudatio penned for this blog post.

Christos Papadimitriou’s body of work is of amazing breadth and depth, and has had a profound and lasting influence on many areas of Computer Science.

In an era of great specialization, Christos Papadimitriou stands out as a present-day Renaissance man. He is an intellectual who, citing the title of one of his essays, is not afraid of asking "big queries" and  applies the “computational lens” to shed light on important problems in several areas of scientific enquiry, ranging from economics to the theory of evolution. While doing what he might himself call “extroverted Computer Science”, he has contributed truly seminal work to a large number of fields within our subject, including algorithmics, complexity theory, computational game theory, database theory, internet and sensor nets, optimization and robotics.

Christos Papadimitriou is also one of the very best expositors and teachers within our field. He has written classic textbooks on the theory of computation, combinatorial optimization, database concurrency control, computational complexity and algorithms. In so doing, he has helped to inspire several generations of computer scientists.

If that wasn't enough, Christos Papadimitriou is a tireless expositor and is able to explain the beauty of our discipline to a general educated public. He is not afraid to cross boundaries, and to use literary forms such as novels (see "Turing: A Novel About Computation", http://mitpress.mit.edu/books/turing-novel-about-computation) and comics (see the graphic novel "Logicomix", http://en.wikipedia.org/wiki/Logicomix) to offer accessible expositions of the science of computing and its origins.

To sum up, Christos Papadimitriou is one of those rare scientists who combines a large, influential and varied body of scientific results with the gifts of an inspiring teacher and of a great communicator.

Monday, January 26, 2015

Associate/Full Professor Position at Oxford in Algotithms or Complexity

The Department of Computer Science at the University of Oxford is planning to make an appointment at associate/full professor level with effect from 1 September 2015 or as soon as possible thereafter. Applicants should hold a PhD in computer science or a related subject and have experience in any area related to algorithms or complexity.  

The details are here

Please help spread the word.