Friday, January 19, 2018

Most Influential POPL Paper Award 2018: "Multiparty asynchronous session types" by Kohei Honda, Nobuko Yoshida and Marco Carbone

I heard the great news that the paper Multiparty asynchronous session types by the late Kohei Honda, Nobuko Yoshida and Marco Carbone has received the Most Influential POPL Paper Award 2018. See

This award is given annually to the author(s) of a paper presented at the Symposium on Principles of Programming Languages (POPL) held 10 years prior to the award year. The papers are judged by their influence over the past decade.

The citation for the award is available from the above-mentioned web page, but I repeat it here for ease of reference:

Session types are a type-based framework for codifying communication structures and verifying protocols in concurrent, message-passing programs. Previously, session types could only model binary (two-party) protocols. This paper generalizes the theory to the multiparty case with asynchronous communications, preventing deadlock and communication errors in more sophisticated communication protocols involving any number (two or more) of participants. The central idea was to introduce global types, which describe multiparty conversations from a global perspective and provide a means to check protocol compliance. This work has inspired numerous authors to build on its pioneering foundations in the session types community and has initiated many applications of multiparty session types in programming languages and tools. It has also influenced other areas of research, such as software contracts, runtime verification and hardware specifications.

Congratulations to the authors of the paper and to the concurrency community at large, whose work over the last ten years contributed to this award and, most importantly, to significant scientific advances that are now embodied in programming languages and tools that are already having practical impact (see the work with Cognizant, Red Hat, and VMWare on Scribble, and with the OOI), and that I believe will find increasing application in years to come. 

Wednesday, January 17, 2018

Five Postdoctoral positions in Computer Science at Gran Sasso Science Institute

Five Postdoctoral positions in Computer Science at
Gran Sasso Science Institute in L'Aquila (Italy)
Deadline:  2 March 2018 at 6 p.m. (Italian time zone)

The Gran Sasso Science Institute (GSSI,, a recently established international PhD school and a centre for advanced studies in computer science, mathematics, physics and social sciences offers 18 postdoctoral research positions, five of which are dedicated to computer science and more specifically to themes that are strongly connected to the pillars of the PhD program in computer science:

- Algorithmic foundations of social and computer networks.
- Software systems and services.
- Specifications and analysis of concurrent reactive systems

The research grants are awarded for two years and their yearly amount is € 36.000,00 gross.

Candidates who are preparing their doctoral thesis are eligible to apply; however, they must have obtained their PhD degree before taking up their appointment with GSSI. Selected candidates are expected to start their appointments no later than 1 November 2018.

The application must be submitted through the online form available at by 2 March 2018 at 6 p.m. (Italian time zone).
Each application should include the following material:

- the CV of the applicant,
- a research statement,
- up to 3 publications and
- the name and email of two references.

For more information, please consult the Call for Applications at or write an email to

Prospective candidates are also welcome to contact Luca Aceto (luca.aceto AT or Michele Flammini (michele.flammini AT 

Friday, January 12, 2018

PhD positions at the School of Computer Science, Reykjavik University

The School of Computer Science at Reykjavik University is advertising PhD scholarships. See for details.

The Icelandic Centre of Excellence in Theoretical Computer Science is one of the research centres within the school and is seeking PhD candidates in the following fields: logic and concurrency (contacts: Anna Ingolfsdottir and Luca Aceto), algorithms and distributed computing (contacts: Eyjólfur Ingi Ásgeirsson and Magnús Már Halldórsson), combinatorics and automated proofs (contact: Henning Ulfarsson), types and programming-language semantics (contact: Tarmo Uustalu).

Friday, January 05, 2018

Call for nominations for the 2018 Alonzo Church Award

Catuscia Palamidessi asked me to post the call for nominations for this year's Alonzo Church Award for Outstanding Contributions to Logic and Computation. I encourage all members of the community to nominate their favourite paper or small group of papers in logic and computation published within the past 25 years.

The 2018 Alonzo Church Award for Outstanding Contributions to Logic and Computation
Call for Nominations
An annual award, called the Alonzo Church Award for Outstanding Contributions to Logic and Computation, was established in 2015 by the ACM Special Interest Group for Logic and Computation (SIGLOG), the European Association for Theoretical Computer Science (EATCS), the European Association for Computer Science Logic (EACSL), and the Kurt Gödel Society (KGS). The award is for an outstanding contribution represented by a paper or by a small group of papers published within the past 25 years. This time span allows the lasting impact and depth of the contribution to have been established. The award can be given to an individual, or to a group of individuals who have collaborated on the research. For the rules governing this award, see:
The 2017 Alonzo Church Award was given jointly to Samson Abramsky, Radha Jagadeesan, Pasquale Malacaria, Martin Hyland, Luke Ong, and Hanno Nickau for providing a fully-abstract semantics for higher-order computation through the introduction of game models, see:
Eligibility and Nominations
The contribution must have appeared in a paper or papers published within the past 25 years. Thus, for the 2018 award, the cut-off date is January 1, 1993. When a paper has appeared in a conference and then in a journal, the date of the journal publication will determine the cut-off date. In addition, the contribution must not yet have received recognition via a major award, such as the Turing Award, the Kanellakis Award, or the Gödel Prize. (The nominee(s) may have received such awards for other contributions.) While the contribution can consist of conference or journal papers, journal papers will be given a preference.
Nominations for the 2018 award are now being solicited. The nominating letter must summarise the contribution and make the case that it is fundamental and outstanding. The nominating letter can have multiple co-signers. Self-nominations are excluded. Nominations must include: a proposed citation (up to 25 words); a succinct (100-250 words) description of the contribution; and a detailed statement (not exceeding four pages) to justify the nomination. Nominations may also be accompanied by supporting letters and other evidence of worthiness.
Nominations should be submitted to by March 1, 2018
Presentation of the Award
The 2018 award will be presented at ICALP 2018, the International Colloquium on Automata, Languages and Programming. The award will be accompanied by an invited lecture by the award winner, or by one of the award winners. The awardee(s) will receive a certificate and a cash prize of USD 2,000. If there are multiple awardees, this amount will be shared.
Award Committee
The 2018 Alonzo Church Award Committee consists of the following five members: Thomas Eiter, Javier Esparza, Catuscia Palamidessi (chair), Gordon Plotkin, and Natarajan Shankar.

Tuesday, December 26, 2017

First-year computer science students at the GSSI publish paper at ICSE 2018

The paper "FAST Approaches to Scalable Similarity-based Test Case Prioritization" by Breno Miranda (UFPE, Brazil), Emilio Cruciani (GSSI, Italy), Roberto Verdecchia (GSSI, Italy, and Vrije Universiteit Amsterdam, NL) and Antonia Bertolino (ISTI - CNR, Italy) has been accepted as a technical research paper at ICSE 2018, the 40th International Conference on Software Engineering. ICSE is the flagship conference in Software Engineering and is very selective its technical-research-paper track is the most prestigious one within the conference.

The paper contributes to the classic area of software testing, which is one of the approaches developed by computer scientists to increase their confidence that computing systems actually do what they were designed to achieve. Since the number of tests that can be performed on a computing system is enormous, test-case prioritization is a crucial element in any practical testing framework. In that approach, one prioritizes test cases so that they can detect faults more efficiently using the available limited resources.

The paper to be presented at ICSE 2018 is the first that applies techniques from data mining to test case prioritization. In particular, it shows that the use of ideas from locality-sensitive hashing, a technique stemming from research in TCS that has been employed to great effect in approximate similarity searches in audio and video data, amongst others, leads to effective test prioritization in practice, when one needs to select tests effectively amongst millions of possible ones.

Antonia Bertolino is a member of the Scientific Board for the PhD programme in Computer Science at the GSSI. Breno Miranda is currently a postdoctoral researcher in Brazil and is one of Antonia Bertolino's former PhD students. Emilio Cruciani and Roberto Verdecchia just started their second year as PhD students in computer science at the GSSI and the paper to be presented at ICSE 2018 builds on their project for the first-year Software Testing course held in early 2017 at the GSSI by Antonia Bertolino. The project itself arose from a question asked by the students during the lectures. This is what inspiring, research-based teaching can produce when there is intellectual chemistry between lecturers and students.

Congratulations to the authors (and to the computer science group at the GSSI)!

Wednesday, December 13, 2017

Tenure-track positions in CS at Reykjavik University

We are aggressively recruiting new tenure-track faculty in Computer Science to Reykjavík University ( Theoretical computer science is one of the focus areas mentioned in the call. This is a link to further information:

Whereas Reykjavík University is relatively small, I believe we can offer junior faculty attractive opportunities and an independent career path. Reykjavík is a great place for families to live, has a vibrant cultural scene and is attractive to people who enjoy the outdoors.

I would very much appreciate your help in getting this job announcement seen by interested potential candidates.

Tuesday, December 05, 2017

A letter to Franklin Foer (guest post by Frits Vaandrager)

Frits Vaandrager has sent the appended letter, which I am posting with his kind permission, to the journalist Franklin Foer. (The letter is also available here.)

Frits wrote to me saying that:
Franklin Foer published an interesting book, World without Mind, that was named a "Notable book of 2017" by the New York Times. According to Foer,  computer scientist started to use the term "algorithm" because of "status anxiety", as a form of name dropping by programmers to suggest that they were also serious scientists. In my letter to Foer I give some historic evidence that this framing is utterly incorrect, but I'd be interested in the views of colleagues from the TCS community on this matter.
Please share your views on this matter as comments to this post. It is important to put the record straight and I am glad that Frits took the time to write a cogent letter to Mr. Foer. Thank you!

Dear Mr Foer,

With much interest I have read your book “World without mind”. I agree with many of your conclusions! But as a computer scientist who has been working on algorithms for more than 30 years, I am also deeply troubled by one paragraph in your book: 

“For the first decades of computing, the term “algorithm” wasn’t much mentioned. But as computer science departments began sprouting across campuses in the 60s, the term acquired a new cachet. Its vogue was the product of status anxiety. Programmers, especially in the academy, were anxious to show that they weren’t mere technicians. They began to describe their work as algorithmic, in part because it tied them to one of the greatest of all mathematicians – the Persian polymath Muhammad ibn Musa al-Khwarizmi, or as he was known in Latin, Algoritmi. During the 12th century, translations of al-Khwarizmi introduced Arabic numerals to the west; his treatises pioneered algebra and trigonometry. By describing the algorithm as the fundamental element of programming, the computer scientists were attaching themselves to a grand history. It was a savvy piece of name-dropping: See, we’re not arriviste, we’re working with abstractions and theories, just like the mathematicians!”
Do you have historic sources for these strong statements? 

Much of computer science is rooted in the work of mathematicians and logicians such as Turing, Church and von Neumann. These researchers used the word “algorithm” already before computers were built, see for instance p349 of Alonzo Church’s 1936 paper “An unsolvable problem of elementary number theory”. Together with Turing’s 1936 paper “On computable numbers, with an application to the entscheidungsproblem”, this paper forms the basis for the so-called Church-Turing thesis, which in turn laid the foundation of theoretical computer science. The computer science pioneers definitely knew the term “algorithm”!!

The term “algorithm” was maybe not used so often by computer scientists during the initial years (often they used terms such as “effective procedure” or “computable function”), but that certainly changed in 1958 with the influential work on ALGOL (short for Algorithmic Language), a family of imperative computer programming languages. The researchers who worked on Algol e.g. Bauer, Backus, Dijkstra, Perlis, Naur, van Wijngaarden & McCarthy were established scientists who definitely did not suffer from “status anxiety”. Backus, Dijkstra, Perlis, Naur and McCarthy later received the Turing award, the major prize for computer science research, for their groundbreaking research.

In order to appreciate the wonderful scientific work on algorithms, I can recommend you, for instance, to read the book Algorithmics – The spirit of computing by David Harel. I hope that, after studying this book, you will be also convinced that the fact that programmers used the term algorithm is not a form of name dropping. The work on algorithms since the advent of computers very much fits into the tradition of the work started by great scientists like Euclides and al-Khwarizmi.

Scientific knowledge may always be used for both good and bad things. Like you, I am very concerned about the use of algorithms by Google, Facebook, Apple and Amazon. But I disagree with any suggestion that there is no science behind computer science algorithms!

Looking forward to your reaction, with best regards,

Frits Vaandrager
Professor of Computer Science at Radboud University
Nijmegen, December 4, 2017