Thursday, April 02, 2015

CONCUR 2015 Deadline approaching

The deadline for CONCUR 2015 is approaching fast:
  • Submission of Abstracts: April 13th, 2015;
  • Submission of Papers: April 20th, 2015 (firm).
Note that you can submit your abstracts at any time before April 20. 

The usage of pdflatex and the LIPIcs style file are mandatory: no changes to font size, page geometry, etc. are permitted. Authors are invited to submit a draft of at most 13 pages including references. Submissions not in the correct format or submitted after the deadline will not be considered.

Tuesday, March 31, 2015

Ode to the Automata Tutor

I am slowly emerging from teaching a first year course on topics in Discrete Mathematics to about 250 students at Reykjavik University. (I have one more lecture to deliver after Easter and then the not-so-small matter of over 200 exam papers to grade :-() This is the second discrete mathematics course the students take and it is the second spring semester in a row that I teach it.

As part of the course, I am supposed to cover  the basics of grammars, finite automata and regular expressions. This is a first year course, so I do not cover much of the theory related to these formalisms and their connections. Mostly I expect the students to be able to design grammars, finite automata and regular expressions for some relatively simple languages.

In both editions of my course, which has been followed by about 500 students overall, I have used the AutomataTutor to support my teaching of material related to finite automata and to grade student assignments automatically.

For what it is worth, I strongly encourage my readers to try the tool and to use it in their undergraduate courses. In my experience, the students love to learn DFA and NFA programming using the Automata Tutor and to work on assignments that employ it. The automatic feedback and grading provided by the Automata Tutor are almost magical. (See this paper for a description of how the tool does both.) This is how the construction of finite automata that recognize regular languages should be taught in a modern way! I wish I had similar tools for all the topics I need to cover in that course.

From my perspective (and from that of my TAs), automatic grading is a real bonus. I love to teach, but I really hate to grade a large number of student assignments. Students can be very creative in their solutions and grading them is a very time consuming, haphazard and inconsistent process for any human. The algorithms embodied in the Automata Tutor produce consistent results at the press of a button and the students receive a grade straight away as well as excellent hints on how to improve incorrect solutions.

Thanks to Rajeev Alur, Loris D'Antoni, Sumit Gulwani, Dileep Kini, Mahesh Viswanathan and their co-workers, teaching basic finite-automata theory to hordes of first-year students can now (largely :-)) be done without tears. To boot, the folks at Automata Tutor have always been ready to provide technical help, when that was needed.

I'll keep using the Automata Tutor in my courses and I hope that you will do so too. That is the best way to thank our colleagues for the work they have done and are still doing on that tool.

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

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,

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