Friday, December 23, 2016

Mariangiola Dezani-Ciancaglini: 70, but still going strong

Mariangiola Dezani-Ciancaglini, one of the most influential Italian (theoretical) computer scientists, turned 70 yesterday. As witnessed by her DBLP entry, Mariangiola is still very active in research and is a prime example of a scientist who continues to challenge herself, to produce excellent work and to mentor young researchers at an age at which many are retired.

The purpose of this post is to celebrate Mariangiola's 70 birthday, hoping that some of the readers of this blog who are not familiar with her work will be tempted to read it and to spread it amongst their students.

Mariangiola Dezani has been one of the leading researchers in the foundations of programming languages and, in particular, of their type systems for about 40 years. She has offered seminal contributions to that field, introducing new type systems that deeply influenced theoretical developments and its practical applications.

In addition to her outstanding research activities, she has been a mentor and role model for young researchers, many of whom now have leading positions at high-class universities. Moreover, she has tirelessly supported female students and researchers in computer science at all stages of their career. She has turned the Department of Computer Science at the University of Turin, Italy, into a hotbed of research on the theory of programming languages. The group led by Simona Ronchi Della Rocca and her is one of the largest research teams in that field in the world, and is one of those with largest percentage of female researchers and students.

Mariangiola's research activity over the years has followed a path in which theoretical developments have been inspired by the evolution of programming languages: from lambda-calculus models in the 1980s, providing foundations for functional programming languages, to object orientation in the 1990s, to dynamic and distributed contexts with behavioural types for web services and session types since the year 2000.

Mariangiola's main scientific achievement in the first phase of her research career was the introduction of intersection type assignment systems, which were largely used as finitary descriptions of models of the lambda-calculus. Intersection types are one example of a theoretical concept developed by Mariangiola Dezani that has later had profound influence on the practice of programming languages. Indeed, their use in the typing discipline for a language has allowed compilers to generate more efficient code for different instantiations. In object-oriented languages, intersection types are employed, amongst other things, in expressing mixins (constructs that permit code reuse avoiding the ambiguities of multiple inheritance). They have also been advocated and are used for manipulating XML and semi-structured data in languages such as CDuce.

Since the year 2000, Mariangiola's research has been mainly devoted to the study of self-adapting types for ensuring safety and liveness of communication protocols also in presence of unexpected events. This work has offered seminal contributions to the study of session types and has led to practical applications whose impact will be felt for years to come. Mariangiola first proposed a formalisation of Java with session types, which was later applied to the design and implementation of SJ (Session Java). These contributions initiated a flurry of research activity aiming at applying session types to many real-world programming languages. She also first studied a theory of progress in the session types for the pi-calculus, whose core theory was later extended to multi-party session types. This formalism became the core of the current version of an open-source protocol description language, Scribble, which is developed at Red Hat and Imperial. This language is used in the multi-million-USD Ocean Observatory Initiative project, whose purpose is to build an infrastructure of sensors and other computing devices located on the ocean floor so that oceanographers to get data about the health of the marine ecosystem. This is an example of the effectiveness and practical impact of the deep and elegant theoretical work carried out by Mariangiola Dezani.

A belated happy 70th birthday, Mariangiola!

Monday, December 05, 2016

Great hiring opportunities for female researchers at the University of Groningen

Jorge A. Pérez asked me to post this very interesting opportunity for tenure-track positions at the University of Groningen, targeted to talented female researchers (see Feel free to contact Jorge if you work in areas related to "Fundamental CS" (using the terminology in the call) and are interested in applying.

Rosalind Franklin Fellowships at the University of Groningen

The University of Groningen (The Netherlands) initiated the prestigious Rosalind Franklin Fellowship programme to promote the advancement of talented international researchers at the highest levels of the institution. The ambitious programme has been running since 2007 and has financed over 90 Fellows.

The Rosalind Franklin Fellowship programme is aimed at women in industry, academia or research institutes who have a PhD and would like a career as full professor in a European top research university. The Fellowship is only awarded to outstanding researchers. New Fellows are given:
  • A tenure track position to work towards full professorship within a period of ten years;
  • Budget for a PhD student to enable them to make a flying start.
Successful candidates will be expected to establish an independent, largely externally funded research programme in collaboration with colleagues at
our University and elsewhere.

The University of Groningen has 13 tenure track positions available in this programme, currently co-funded by the European Union.
Within these, the Faculty of Mathematics and Natural Sciences (FMNS) has five Rosalind Franklin Fellowships to offer, including positions on
  • Fundamental Computer Science (Data Management, Theory of Computing, Algorithms, Networks, Security)
  • Artificial Intelligence (logic, neuromorphic computing, cognitive modelling or robotics)
  • Fundamental Mathematics (Algebra, Geometry, Analysis), Mathematical Data Analysis, Complex Systems
Ambitious female academics are invited to apply for these positions before February 1, 2017.

More information about the positions (including eligibility conditions and conditions of employment) is available on:

See also:
- The applicants guide:

- The Johann Bernoulli Institute for Mathematics and Computer Science:

Martino Lupini receives the 2015 Sacks Prize of the Association for Symbolic Logic

The 2015 Sacks Prize of the Association for Symbolic Logic for the best doctoral dissertation in Logic will be shared by Omer Ben-Neria, University of California, Los Angeles, and Martino Lupini, California Institute of Technology. The prize citations can be found here and are also appended to this post for ease of reference.  Congratulations to the prize recipients!

Omer Ben-Neria received his Ph.D. in 2015 from Tel Aviv University under the supervision of Moti Gitik.

Martino Lupini received his Ph.D. in 2015 from York University, Toronto under the supervision of Ilijas Farah. He received his bachelor degree at the University of Parma (under the supervision of Celestina Cotti Ferrero) and a master degree from the University of Pisa advised by Mauro Di Nasso with a thesis entitled Recurrence and Szemerédi’s Theorem.

Martino Lupini is the second Italian young researcher to receive this accolade; the first was Matteo Viale in 2006. The successes of young Italian logicians witness the quality of the research in logic in Italy. This is yet another vindication of the analysis of the European Commission on the quality of research in Italian universities, compared with the resources available to Italian researchers: "Strong public science base despite an overall underinvestment in research and innovation." The executive report on Italy also states "R&D investment has slightly increased in recent years but the gap with the EU average is still quite significant." I hope that Italy will devote more of its budget to supporting its universities and research in the future. A starved system cannot continue producing young researchers like Martino Lupini for much longer.

Prize citations

Ben-Neria received his Ph.D. in 2015 from Tel Aviv University under the supervision of Moti Gitik. In his thesis, The Possible Structure of the Mitchell Order, he proved the remarkable result that, under suitable large cardinal assumptions on the cardinal $\kappa$, every well-founded partial order of cardinality $\kappa$ can be realized as the Mitchell order of $\kappa$ in some forcing extension. The Prizes and Awards Committee noted that the proof is a tour de force combination of sophisticated forcing techniques with the methods of inner model theory.

Lupini received his Ph.D. in 2015 from York University, Toronto under the supervision of Ilijas Farah. His thesis, Operator Algebras and Abstract Classification, includes a beautiful result establishing a fundamental dichotomy in the classification problem for the automorphisms of a separable unital $C^*\/$-algebra up to unitary equivalence, as well as a proof that the Gurarij operator space is unique, homogeneous, and universal among separable 1-exact operator spaces. The Prizes and Awards Committee noted that his thesis exhibits a high level of originality, as well as technical sophistication, in a broad spectrum of areas of logic and operator algebras.

Alonzo Church Award 2017: Call for Nominations

Gordon Plotkin asked me to post the call for nominations for the 2016 Alonzo Church Award for Outstanding Contributions to Logic and Computation. The first edition of the award was given to Rajeev Alur and David Dill for their invention of timed automata, see: I strongly encourage members of the community to nominate their favourite paper(s) for this accolade. See the call for the rules regarding eligibility and on how to submit your nomination. 

The 2017 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 2016 Alonzo Church Award was given to Rajeev Alur and David Dill for their invention of timed automata, see:

Eligibility and Nominations

The contribution must have appeared in a paper or papers published within the past 25 years. Thus, for the 2017 award, the cut-off date is January 1, 1992. 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 2017 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 are due by March 1, 2017, and should be submitted to

Presentation of the Award

The 2017 award will be presented at the CSL conference, the annual meeting of the European Association for Computer Science Logic. 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 2017 Alonzo Church Award Committee consists of the following four members: Natarajan Shankar, Catuscia Palamidessi, Gordon Plotkin (chair), and Moshe Vardi.

Monday, November 21, 2016

Academic evaluation and hiring in Italy: The curious incident of Giovanni Sambin in the ASN 2016

Disclaimer: This post might contain imprecisions about the ASN, since I have never worked at an Italian university myself and I have never applied for the Italian ASN. I welcome corrections from whoever reads this post and has experience with this Italian evaluation exercise. Let me state at the outset that what I write pertains to fields such as computer science and mathematics. I do not know what is done in the humanities. 

An Italian law dated 30 December 2010 specifies a procedure for academic hirings in Italy at the level of associate and full professor. According to that law, recruiting for those positions should be "based on scientific qualification criteria. A national commission evaluates and assesses the candidates scientific qualification." See this outdated web site, which should be compared with the one in Italian.  Only candidates that have obtained the so-called Abilitazione Scientifica Nazionale (ASN, National Scientific Qualification) can then apply for a professor position at an Italian university, if and when such positions are advertised.

One can wonder why Italy uses this two-step system for academic hirings, whose need is not felt in any of the countries where I have worked so far. I guess that the first step is meant to filter out potential candidates who do not meet minimum requirements for being a professor at any of the 63 public universities in Italy. 

According to the regulations a "national commission evaluates and assesses the candidates scientific qualification." In fact, there is one national commission for each of the many scientific areas considered in Italy. Many of these commissions have to examine hundreds of applications, and their members play the role of gatekeepers and paladins of quality in the Italian university system. I can only imagine how much work is needed to do a thoughtful job in one of those committees and how easy it is to make enemies regardless of how considerate one is in justifying one's opinions. The evaluation is partly based on bibliometric criteria, which are known beforehand, should simplify the work of the commissions and should give a look of objectivity to their decisions. However, as far as I know, the commissions can also base their decisions on a qualitative analysis of the applicants.

Given the crucial role played by the members of the evaluation committees, one would expect that their members are chosen by taking the candidates' scientific profile and experience carefully into account. As it turns out, however, the qualifications of candidates for the committee are evaluated using only the following three bibliometric criteria:
  1. Number of publications in the period 2006-2016 (threshold 9);
  2. Total number of citations  in the period 2001-2015 (threshold 80);
  3. H-index in the last 15 years (threshold 5). 
In order to be eligible, one has to meet the thresholds in at least two of the above criteria. This might even seem reasonable. Note, however, that only publications indexed in Web of Science or Scopus count. In particular, journal papers published in outlets that are not indexed by Web of Science/Scopus are not taken into consideration (regardless of their content and impact) and conference papers don't count at all. Books and monographs don't count either, regardless of how influential they might be. Web of Science/Scopus are also used for calculating citations and the h-index. Again, this provides a smaller coverage than the one offered by Google Scholar, say.

By way of example, recently Giovanni Sambin, one of the most famous, currently active Italian logicians and an expert academic  one would trust to lead a national evaluation committee for Mathematical Logic, was considered to be ineligible as an evaluator because he met only one of the above-mentioned criteria. His Google Scholar profile is here.

This kind of decisions makes me wonder whether there is an overemphasis on bibliometric evaluations in Italian academia. If experience over a long and distinguished academic career plays second fiddle to fairly arbitrary thresholds calculated using only Web of Science and Scopus, I wonder how reliable the decisions of the evaluation committees will be considered by Italian academics. Most importantly, having so many people spend a lot of time seeking the holy grail of the national qualification and small committees devote endless hours examining their qualifications looks like a huge waste of energy and resources. I cannot help but think that that energy and time would be best used for research, teaching and all the other tasks that make up our work.

Tuesday, November 15, 2016

Workshops at LICS 2017

The following six workshops will be co-located with LICS 2017 and will take place on Monday, 19 June 2017, on the premises of Reykjavik University:
  • WiL: Women in Logic. Proposers: Valeria de Paiva, Amy Felty, Anna Ingolfsdottir, Ursula Martin
  • LCC: Logic and Computational Complexity. Proposers: Norman Danner, Anuj Dawar, Isabel Oitavem, Heribert Vollmer
  • LMW: Logic Mentoring Workshop. Proposers: Anupam Das, Valeria Vignudelli, Fabio Zanasi
  • LA: Learning and Automata. Proposers: Borja Balle, Leonor Becerra-Bonache, Remi Eyraud
  • LOLA: Syntax and Semantics of Low-Level Languages. Proposer: Matija Pretnar, Noam Zeilberger
  • Metafinite model theory and definability and complexity of numeric graph parameters. Proposers: Andrew Goodall, Janos A. Makowsky, Elena V. Ravve.
More details on this workshops will be available from the conference web page in due course. I hope that you'll consider attending them and submitting excellent papers to the conference. 

Wednesday, November 09, 2016

What makes a research institution excellent?

Some time ago I stumbled across the video of the panel discussion "IST Austria: On the Way to the Top: What Makes a Research Institution Excellent?". (There is also a much shorter, 11-minute version of the video here.) I watched the discussion with great interest, and found it inspirational and thought-provoking.

The panelists were Patrick Aebischer (president of EPFL until the end of 2016), Jonathan Dorfan (president of the Okinawa Institute of Science and Technology), Peter Gruss (former president of the Max-Planck-Gesellschaft from 2002 till 2014), Helga Nowotny (former President of the European Research Council), Rolf-Dieter Heuer (Director General of CERN from 2009 to 2015), Haim Harari (President, from 1988 to 2001, of the Weizmann Institute of Science) and Olaf Kübler (former president of ETH Zurich). It doesn't get much better than this, in terms of experience about the subject matter and, if you are interested in the topic or even just in hearing experienced academics discuss it, I'd encourage you to have a glass of your favourite beverage, relax and have a look. It is remarkable how much agreement there was in isolating the key ingredients leading to research excellence.

Here is my quarter-baked summary of some of the contributions, with apologies for not covering the whole discussion, possibly biased reporting and for any error I might have made.

Patrick Aebischer stated that Europe lacks super-brands such as Berkeley, CalTech, CMU, Harvard, MIT and Stanford. One needs elite universities to attract talents. The US attracts the best graduate students, the best young researchers with their tenure-track system and also people in high-ranking management positions. He also mentioned that to foster excellence, it is useful to have some competition between public and private universities. He said that integration of research and education is key to achieve excellence, as are attracting and keeping the best faculty, and giving early independence to young individuals. 
In order to achieve excellence, funding must be significant. A flexible organizational structure is needed to be able to compete at the highest level.
In this era, one can rise fast, but one can also fall faster than before.
Peter Gruss started by asking a fundamental question: what makes creative research possible? In his words, it is amazing how easy the answer is and how difficult it is to achieve it: "Hire the most brilliant minds and give them everything they need to stay brilliant." That's it.

He referred to the work of the historian Rogers Hollingsworth who isolated the following ingredients for excellence in research institutions:
  1. Excellence in research and leadership. On this point, Gruss said that is critical that one hires top people because top people hire people who are better than themselves. To get them, one has to do head hunting plus advertising. One should strike a good balance between tenured and non-tenured people to maintain flexibility.
  2. Small research settings.
  3. Small group size, but large context.
  4. Multidisciplinary contacts. One has to install interfaces between different disciplines. (Examples: Have only one coffee room.)
  5. Independence as early as possible. Give young people stability for a certain period of time to allow them to unfold their creativity. Coaching and mentoring of young researchers must be provided.
  6. Core institutional and flexible funds. There should be a balance between high-trust and low-trust funding. When handing out high trust funding, an agency must trust the funded institution: Give them the money that you can afford and let them do what they want with it. Trust them to make the most of the received funding. 
He also mentioned that a study in the US pointed out that 75% of citations in patents are to papers funded by public money. Of this 75% of papers most of them belong to the top10% of the papers cited within the scientific community. Hence one should invest in research, in fact, in top research. Hire the best without compromise. Put a lot of weight on top scientists.

Rolf-Dieter Heuer mentioned the importance of "taking society with you." One has to promote science in society.

For research, one needs to continuously develop a vision, which will drive innovation and technology, partnership with industry and feed back to research. Every excellent institution must keep this virtuous circle.  One must think strategically and long term.

All staff needs to have intellectual challenges, including administrative staff. Excellence can be in individuals, but also in cooperation. Excellence must allow for failure, for some research that might fail. This is doing science at the edge. What one can guarantee is that the path will be fruitful.

Olaf Kuebler stated that the strategy to create a leading research institution is deceptively simple: "Search, appoint and retain world-leading scientists. All else will follow."

The reputation of a university is made by the people who leave the university students, graduate students, assistant professors etc.

He also stated that an excellent research institution must:
  1. Make significant contributions to themes of global importance.
  2. Identify and develop new themes of global importance. 
  3. Harmonize its portfolio with its funders.
Helga Nowotny said that being open towards the future is the key aspect of excellence. Invest in excellent young people, who are competent rebels and understand that scientific knowledge is always preliminary. One has to bear in mind that excellence is always a multi-dimensional concept.
One should provide the best possible working conditions. This involves
  • a space component: space that makes it almost obligatory to run into each other and discuss, as ideas emerge by talking to each other, and 
  • a time component: give time for the unexpected, for the unforeseen, for serendipity.

Jonathan Dorfan mentioned that one should establish a setting that is conducive for inter-disciplinary research, where researchers from different fields can cooperate and exchange ideas.

Haim Harari closed the meeting with an articulate and thought-provoking short address. He started by pointing out what he considers to be key ingredients for an excellent research institution. 

Funding must be versatile and come from many sources. Only if one is versatile one can have the right mix. Government funding leads inevitably to egalitarianism  and democracy. However, science is not democratic. Still there has to be a balance between the power of the president and the faculty.

A research institution should be as international as possible and as national as possible. It should give something back to the taxpayers: education and touching society. Technology transfer is the other thing one return to society.

The Weizmann Institute put all the different subjects in the same campus, which leads to inter-disciplinary research that cannot be done by any single subject alone. 

Harari also said that the excellence of a research institution should be evaluated according to  three different measures:
  1. its best ten people,
  2. the average quality of its professors and
  3. its worst professor.
The quality of the worst professor says what the threshold of the institution is for hiring and is a very important indicator of the standards of the research institute/university.

In Harari's opinion, the president of a research institute/university should regularly ask herself/himself: If I could fire some of my professors, how many would I fire?" If the number is a non-trivial fraction of the faculty, then the threshold of the institution is not high enough.

So, in your opinion, what makes a research institution excellent?

Friday, October 21, 2016

October issue of the Bulletin of the EATCS

The October 2016 issue of the EATCS Bulletin is now available online at, featuring the following interesting columns
If you prefer the whole issue, you can download a pdf with the printed version of the bulletin from

As usual, thanks to the support of the EATCS members, the EATCS Bulletin is published in open access form. Consider joining the association!

Friday, October 07, 2016

Ágnes Cseh receives one of the 2016 Klaus Tschira Awards for Achievements in Public Understanding of Science

It is fair to say that not many computer scientists try to present innovative research findings in a way that is accessible to an interested, but rather unspecialized, public. Even fewer succeed and the rewards for those who do are relatively minor. As a consequence, the number of essays and books about computer science that have a wide readership is substantially smaller than those about astronomy and physics, say. In my humble opinion, this is a pity, since many of intellectual achievements of computer science research deserve to be known by any intellectually curious layperson.

I was therefore happy to learn about the Klaus Tschira Award for Achievements in Public Understanding of Science. Since 2006, the Klaus Tschira Stiftung has looked for young scientists who can write a generally understandable article (8,000 to 9,000 words) in German about their research and the content of their PhD thesis. The prize is awarded in each of biology, chemistry, information technology, mathematics, neurosciences and physics as well as in closely related fields. The contributions are judged by a panel of experts on science and communication, which selects the winners based on scientific quality and on how well the scientific contribution is presented in a way that is amenable to public understanding. Yearly, up to six winners receive the award, which is endowed with prize money of 5,000 Euros. The prize-winning contributions are published in a supplementary issue of the popular science magazine bild der wissenschaft (German). Moreover, all competitors are off ered a participation in a two-day workshop for science communication.

The piece by Ágnes Cseh (a former postdoc of Magnús M. Halldórsson's at ICE-TCS, Reykjavík University) you can find here is the English translation of the German original that was selected as one of the prize-winning contributions for 2016. (It will appear in the October issue of the Bulletin of the EATCS.) It is based on Ágnes’ PhD thesis Complexity and algorithms in matching problems under preferences, which she defended in 2015 under the supervision of Martin Skutella at TU Berlin. I am sure that you will enjoy reading it as much as I did, regardless of whether you believe that algorithms can help us find stable marriages in real life.

Thursday, October 06, 2016

The calls for nominations for most of the EATCS-related awards are out

As usual, the EATCS has issued its calls for nominations for the 2017 edition of most of its awards with deadline 31 December 2016. You can find the calls on the EATCS web page, but I collect them below for ease of reference.
The calls for the Alonzo Church Prize and the Gödel Prize, which the EATCS  awards jointly with other associations, will follow.

Let's make the job of the award committees difficult by nominating some of the many colleagues who would richly deserve the awards for these accolades!

Friday, September 30, 2016

CS@Aalborg University: Research evaluation 2011-2015

Every five years, the Department of Computer Science at Aalborg University undergoes a research evaluation. The purpose of this exercise is to provide the department with qualified and independent opinions on its "actual research topics, results, and performance, but also on strategic issues like funding, internal organization and synergies, possible new directions, collaboration with industry, internationalization, positioning IT as a key enabler in society, etc." So the overall aim is to improve the quality and impact of the research carried out within the department.

The evaluation committee for the period 2011-2015 consisted of Peter Apers (University of Twente, the Netherlands), Jan Gulliksen (KTH Royal Institute of Technology, Stockholm, Sweden), Chris Hankin (Institute for Security Science and Technology and Imperial College, UK), Heikki Mannila (Aalto University, President of the Academy of Finland, Finland) and Torben Bach Pedersen (Aalborg University, Denmark), who was the internal member and chair of the committee.

The report resulting from the latest such evaluation has recently been released and can be found here. The editors of the report were Manfred Jaeger, Jesper Kjeldskov, Hua Lu and Brian Nielsen. As a former editor of such a report in days long gone, I know that their job required a considerable use of time and effort.

So, what did the evaluation committee have to say? Quoting from its evaluation of the department as a whole,
"The Computer Science Department has two world-class groups and excellent staff in all groups. The Danish IT benchmarking exercise of 2014 shows that the Department is the best department in Denmark for number of refereed publications and BFI points per full-time faculty member. The Department is also top in a number of other metrics. During the review it was also reported that Aalborg Computer Science graduates are highly prized by industry. The Department thus deserves to be ranked even higher in the QS World University Rankings by Subject or the Academic Ranking of World University (ARWU \Shanghai") Subject ranking. The current rankings are to a large degree caused by the poor coverage of computer science publications in the commercial bibliometric indices used in these rankings (WoS, Scopus). Here, Google Scholar provides a much better coverage. However, the Department clearly has the potential to rise considerably in these rankings but will require support from the Faculty and University to achieve this."
The two world-class groups mentioned in the above quotation are the Database and Programming Technologies and the Distributed and Embedded Systems units. (The latter is now called Distributed, Embedded and Intelligent Systems unit as it now also includes researcers from what used to be the Machine Intelligence group.) Those two groups are led by the Danish computer scientists with the highest h-index, and have a truly impressive publication and grant-winning record.

You can find the committee's evaluations for each of the research groups in the report. Here I'll limit myself to mentioning an excerpt of what the committee wrote about the Distributed and Embedded Systems unit, where I had the pleasure to work for ten years.

"The Distributed and Embedded Systems group is a world-class group. It is involved in a broad range of activities from semantic foundations through tool development for verification and validation to real-world applications. The group is making excellent contributions across the whole spectrum of activity; this is internationally recognized by prestigious awards such as:
  • The ERC Advanced Grant LASSO
  • The 2013 CAV Award for Uppaal - the first time that this award has been granted to a non-US team
  • The ranking of  "Uppaal in a Nutshell" as the 9th most influential paper in Software Engineering since 1972
  • Best paper awards, medals and other awards to Associate Professors
The h-index of Kim Guldstrand Larsen is outstanding and places him among the top echelon of researchers in this area; his h-index is higher than some Turing Award winners in cognate areas. It is also pleasing to note that some of the Associate Professors also have high h-indices for their career point. .....

The group has published well during the review period with 175 conference papers - 75% of which are in A and B venues - and 63 journals - 92% of which are in A and B venues. .....
The group has secured 37 new grants to a total value of DKK103.8M. ....

The major strength of the group is the people; not only the group leader but the strong group of more junior academic staff and an excellent group of support staff. The broad span from foundational work to applications is also unusual in such groups in other universities and is a considerable strength of DES. The profile and reach of the group is enhanced by its dissemination activities but also the engagement of senior staff in policy-related activities at national and European levels."

Of course there is still a lot of room for improvement, but this will require support from the university as a whole, high-profile new hires in the future and the development of the talent the department already boasts. However, the opinion of the evaluation committee clearly highlights the current strength of a CS department that, in my admittedly biased opinion, deserves to be better known worldwide.

Thursday, September 29, 2016

Zoltán Ésik (1951-2016): In Memoriam

The following obituary for Zoltán Ésik will appear in the October issue of the Bulletin of the EATCS and on the web page of Academia Europaea.

Zoltán Ésik (1951-2016)
In Memoriam 

Luca Aceto and Anna Ingólfsdóttir
ICE-TCS, School of Computer Science, Reykjavik University

Our friend and colleague Zoltán Ésik passed away in Reykjavik, Iceland, on Wednesday, 25 May 2016. He was visiting us as he did with some  regularity, compatibly with his many engagements throughout the world. 

The day before his untimely death, Zoltán had delivered an ICE-TCS seminar entitled Equational Logic of Fixed Point Operations at Reykjavik University. At the start of his talk, he looked somewhat tired and out of breath. However, the more he was presenting a research topic that he loved and that has kept him busy for most of his research career, the more he seemed to be feeling at ease. After the talk, we spent some time making plans for mutual visits in the autumn of 2016 and we discussed some EATCS-related matters. His wife Zsuzsa and he were due to spend a few days travelling in the north of Iceland before their return to Szeged, but life had other ideas. 

Zoltán was a scientist of the highest calibre and has left behind a large body of deep and seminal work that will keep researchers in theoretical computer science busy for a long time to come. The list of refereed publications available from his web site at 
includes two books, 32 edited volumes, 135 journal papers, four book chapters, 86 conference papers and seven papers in other edited volumes. However, impressive as they undoubtedly are, these numbers give only a very partial picture of Zoltán's scientific stature. Together with the late Stephen Bloom, Zoltán was the prime mover in the monumental development of Iteration Theories. As Stephen and Zoltán wrote in the preface of their massive book on the topic, which was published in 1993 by Springer:

Iteration plays a fundamental role in the theory of computation: for
example, in the theory of automata, in formal language theory, in the
study of formal power series, in the semantics of flowchart algorithms
and programming languages, and in circular data type definitions.  It
is shown that in all structures that have been used as semantical
models, the equational properties of the fixed point operation are
captured by the axioms describing iteration theories. These structures
include ordered algebras, partial functions, relations, finitary and
infinitary regular languages, trees, synchronization trees, 2-categories,
and others.

It is truly remarkable that the equational laws satisfied by fixed point operations are essentially the same in a large number of structures used in computer science. Isolating those laws, and showing their applicability, has been one of the goals of Zoltán's scientific life and we trust that the members of our community will keep reading his work on iteration theories, which continued and went from strength to strength after Stephen and he published their 600-page research monograph in 1993. During his last talk in Reykjavik, we asked Zoltán whether he was planning to write a new edition of that book, and half-jokingly told him that it would probably be about 1,200 pages.

Zoltán's research output includes contributions to automata theory, category theory, concurrency theory, formal languages, fuzzy sets and fuzzy logic, graph theory, logic in computer science, logic programming, order theory, semiring theory and universal algebra, amongst others. The breadth of research areas to which he has contributed bears witness to his amazing mathematical powers and to his curiosity. Wherever he went and no matter how long he had travelled to get there, Zoltán's brain was always open. 

Zoltán also contributed to the research community with his service work and received several awards. Here we will limit ourselves to mentioning that he was elected member of the Academy of Europe in 2010, was named Fellow of the EATCS in 2016, was a member of the council of the EATCS from 2003 to 2015, and of the Presburger Award Committee in 2015--2016. He represented the Hungarian theoretical computer science community in the International Federation for Information Processing (IFIP) as member of TC1 since 2000 and was one of the prime mover in the establishment of the IFIP WG 1.8, Working Group on Concurrency. He also received the Gy. Farkas Research Award and the K. Rényi Research Award of the János Bolyai Mathematical Society.

Zoltán's appetite for work was phenomenal, but he also liked to have fun, to spend time with friends eating good food and drinking excellent wine, and to travel. Indeed, Zoltán's lust for travel was amazing. We lost track of his visits to myriads of research institutions and universities all over the world. He attended conferences in the most remote locations and always made sure that he would reserve some time for enjoying the most beautiful and known sites. At times, we had the feeling that he had been everywhere in the world.  

Despite being often on the move, Zoltán was very much a family man. He was very proud of his wife Zsuzsanna, their daughter Eszter and their son Robert. He always told us about the latest developments in their lives and was happy about his four grandchildren. We had the pleasure of enjoying Zsuzsanna and Zoltán's exquisite hospitality both in Szeged and in their summer home on Lake Balaton.

Zoltán was very loyal to his friends and would make trips to see them wherever they were living. We were lucky to be amongst them and had the pleasure of hosting him in Aalborg, Florence and Reykjavik, where he visited us a few times and where the thread of his life was cut. We will miss the time we spent doing research or relaxing together, his sense of humour, his conviviality and his hospitality. 

Thursday, September 15, 2016

LICS 2017: Call for Workshop Proposals

                                        Call for Workshop Proposals
                                                  LICS 2017
                                32nd Annual ACM/IEEE Symposium
                                    on Logic in Computer Science


The thirty-second Annual ACM/IEEE Symposium on Logic In Computer Science (LICS'17) will be held in Reykjavik, Iceland on June 20–23, 2017. The workshops will take place on June 18–19, 2017. June 18 will only be used by two-days workshops (if any), or in case the number of workshops is really large. This year, workshop fees should be around 65 euros for a one-day workshop (including lunch and two coffee breaks).

Researchers and practitioners are invited to submit proposals for workshops on topics relating logic – broadly construed – to computer science or related fields. Typically, LICS workshops feature a number of invited speakers and a number of contributed presentations. LICS workshops do not usually produce formal proceedings. However, in the past there have been special issues of journals based in part on certain LICS workshops.

Proposals should include:

        • -  A short scientific summary and justification of the proposed topic.
             This should include a discussion of the particular benefits of the topic to the LICS community.
        • -  A discussion of the proposed format and agenda.
        • -  The proposed duration, which is typically one day (two-day workshops can be accommodated too).
        • -  Procedures for selecting participants and papers.
        • -  Expected number of participants. This is important for the room!
        • -  Potential invited speakers.
        • -  Plans for dissemination (for example, special issues of journals).

Proposals should be sent to Patricia Bouyer:

** Important Dates **

        Submission deadline:    November 1, 2016
        Notification:                   November 15, 2016
        Program of the workshops ready: May 19, 2017
        Workshops:                      June 18–19, 2017
        LICS conference:                June 20–23, 2017

The workshops selection committee consists of the LICS General Chair, LICS Workshops Chair, LICS 2017 PC Chair and LICS 2017 Conference Chair.

Thursday, September 08, 2016

An interview with Paul Spirakis, the new EATCS president

During its annual meeting at ICALP 2016 in Rome, the Council of the EATCS elected Paul Spirakis (University of Liverpool, UK, and University of Patras, Greece) as its new president. Paul is a well-known figure in the theoretical'computer-science community and truly needs no introduction. However, I felt that it might be a good idea to interview him briefly in order to give him the opportunity to present himself to the community and to discuss some of his plans for his mandate as president of the EATCS.

I interviewed Paul Spirakis via email and present his answers to my questions in this interview that will appear in the October issue of the Bulletin of the EATCS. In order to preserve the style of Paul’s answers, I did not edit them. I hope that the readers of this blog and of the Bulletin of the EATCS will enjoy reading the text of the interview and will find it as interesting as I did.

Wednesday, August 24, 2016

Proceedings of ICALP 2016

The proceedings of ICALP 2016 are now available from the LIPIcs web site. Many thanks to all the colleagues who have worked so hard to make this possible.

I hope that many of you will read the papers in the proceedings, which were selected by Davide, Michael, Yuval and  their PCs, and build on their research contributions.

Thursday, July 21, 2016

CAV Award 2016

The CAV Award 2016 was presented today to Josh Berdine, Cristiano Calcagno, Dino Distefano, Samin Ishtiaq, Peter O'Hearn, John Reynolds, and Hongseok Yang for "the development of Separation Logic and for demonstrating its applicability in the automated verification of programs that mutate data structures." This is the second major award that is given for work on Separation Logic in the space of roughly a week. Indeed, Steve Brookes and Peter O'Hearn received the 2016 Gödel Prize last week at ICALP 2016 for their invention of Concurrent Separation Logic. (The retrospective article describing Concurrent Separation Logic starts on page 47.)

The award recipients are honoured for the development of the theory of Separation Logic, which includes the key notion of separating conjunction, the work showing its applicability in the analysis of non-trivial programs, and the tool development that culminated in Facebook Infer.

Congratulations to the award recipients!

Those interested in learning about Separation Logic can consult, for instance, the following resources by Peter O'Hearn:

Tuesday, July 19, 2016

Report on the EATCS General Assembly at ICALP 2016

The annual general assembly of the EATCS was held at ICALP 2016 on Thursday, 14 July, from 16:30 till 18:15. The slides I used for the meeting are here, for those who are interested.

I started the general assembly by apologizing to the audience for the problems we had in making the official LIPIcs proceedings available by the conference date. (A preliminary version of the proceedings was available in the form of three large files, one per track, but those were very large and hard to download at the conference hotel. The EATCS Secretary prepared a dedicated web page from which the files of the individual papers could be accessed,  but this page was available too late.) This ICALP was the first edition of the conference with LIPIcs proceedings and there were some associated teething problems. (ICALP is the largest conference ever to publish its proceedings with LIPIcs, as far as I know.) I am responsible for this problem and promised that it won't happen again.

During the ensuing discussion, Thore Husfeldt mentioned that, based on his experience as editor of a recent LIPIcs proceedings, he realized that we (theoretical computer scientists) are not good at following the given typesetting guidelines and that this makes the work of the proceedings editors and of the LIPIcs staff harder than it needs to be. (In passing, in a comment to this post, Marc Herbstritt from LIPIcs pointed out that some ICALP papers contains flaws that LIPIcs is still trying to resolve as part of publishing a high-quality proceedings volume. He also noted that most of the authors did not comply with the  typesetting instructions they were given, which results in a huge amount of additional work for LIPIcs, and asked: "How come?")

I thanked Thore and asked the audience to help the proceedings chair and the LIPIcs staff by sticking to the typesetting instructions they are given. With electronic proceedings, one or two pages more don't matter and there is no point in trying to gain them by hacking the style files or using fonts that are forbidden by the publisher.

As a counterpoint, Mikkel Thorup and Yuval Rabani stated that they felt authors should not be bothered by strict typesetting guidelines, and that they should spend their time doing good science rather than having to worry about typesetting guidelines from the publishers. Mikkel stated that "if it typesets, it should be good enough". He also suggested that a nice web interface to which authors could upload their papers for checking whether they meet the guidelines of the publisher would be very helpful.

I thanked all the contributors to the discussion. The EATCS will take all the suggestions into account and discuss them with LIPIcs. ICALP will also try to cooperate with other conferences and LIPIcs in order to develop some automated support that can help in preparing the proceedings efficiently and professionally.

I then remembered four colleagues who have left us too early: Hartmuth Ehrig, Zoltán Ésik, David Johnson and Helmut Veith. Obituaries for all these colleagues, apart from Zoltán Ésik, may be found in the June issue of the Bulletin of the EATCS. I trust that contributions honouring the memory of Zoltán Ésik will appear in the October issue of the Bulletin. The EATCS Council decided to offer a small donation to the award in memory of Helmut Veith, established by the University of Vienna to support promising students. As usual, I invite the members of the TCS community to honour the memory of the aforementioned colleagues by building on their work and disseminating it amongst our students.

Tiziana Calamoneri delivered the report from the conference organizers. (Tiziana's slides are here.) ICALP 2016 had 239 registered participants, 205 of whom registered by the early registration deadline. In her presentation, Tiziana also analyzed some of the reasons for the lack of workshops at this year's edition of ICALP.

Yuval Rabani, who chaired the PC for Track A of ICALP,  delivered the report on the PC chairs. (The slides are here.) Yuval said that chairing the PC of Track A was an unexpectedly pleasant experience and thanked his PC for the splendid work it had done. Apart from reporting on the figures related to accepted  and submitted papers, Yuval described the selection process for Track A, building on his blog posts available here. Quoting from Yuval's blog,
The committee identified around 50 borderline papers, and we had to choose among them 5 or 6 papers. (For those familiar with EasyChair - most papers with scores 2, 1, 1 were rejected.) Choosing those 5-6 papers out of 50 or 51 papers took up about half of the discussion time, because it was indeed a difficult choice. We felt that almost all of the borderline papers could have ended up in the program. The final choice was made, in part, by assessing the “added value” to already chosen papers. For 2 of the 6 slots we ended up voting between 2-3 alternatives for each slot (papers in the same area that were thought to be of about the same quality). Aside from these few last papers, we devoted almost no attention to balancing subareas of theory. Papers were accepted based on pure merit, as judged by experts. Despite the indifference to areas, I think the program came out rather balanced between algorithms and complexity theory, with a nice presence in specialized niche areas. This is a natural outcome of a diverse committee.
Immediately after Yuval's presentation, I handed out the awards for the best papers and the best student papers at ICALP 2016.  The best paper awards went to the following papers:
The following papers received the best student paper awards:
Congratulations to the authors of the award-receiving papers!

Mikolaj Bojanczyk gave a short report on the organization of ICALP 2017 on behalf the organizing committee. ICALP 2017 will be held in Warsaw, Poland, in the period 10-14 July 2017. The PC chairs will be Piotr Indyk (MIT, USA) for Track A, Anca Muscholl (LaBRI, France) for Track B and Fabian Kuhn (Freiburg,
Germany) for Track C. Three invited speakers have already been confirmed: Mikolaj Bojanczyk (Warsaw, Poland), Monika Henzinger (Vienna, Austria) and Mikkel Thorup (DIKU, Denmark). A fourth invited speaker will be announced soon.

Mikolaj mentioned that four workshops have already agreed to co-locate with ICALP 2017. If you are interested in organizing a workshop at ICALP 2017, please contact the local organizers.

Jiří Sgall presented a bid to host ICALP 2018, the 45th ICALP,  in Prague in the period July 9-13, 2018. The slides for Jiři's presentation are here. The bid from Prague was accepted by the General Assembly. Thanks to Jiří and his colleagues for their kind offer to host ICALP in the beautiful city of Prague! ICALP 2017 and 2018 will also allow us to celebrate the excellent contributions of the Polish and Czech research communities to TCS and discrete mathematics.

After the ICALP-related presentations, I asked the audience the following questions:
  • Does ICALP cover TCS sufficiently broadly?
  • What do you think of the current acceptance rates at ICALP?
  • What would you like to see at ICALP that we don’t do?
  • Any criticisms/kudos/suggestions?
There were interesting suggestions from several colleagues. In particular, there was a lively discussion related to the role of the current incarnation of Track C. Despite the best efforts of the PC chairs of the last few years to "brand" this track as a "theory of networking" track, it is fair to say that, despite the high quality of the contributed papers, Track C is still being seen by many as a less competitive version of Track A. This opinion was, for instance, aired by Mikkel Thorup. In particular, Mikkel asked: "What is the role of the current Track C rather than allowing PC members for Track A to submit to the conference?" I reminded the audience that Track C was meant to cover "emerging areas" and that its scope should therefore be regularly considered. During the ensuing discussion, Paul Spirakis suggested that perhaps Track C could be solely devoted to Algorithmic Game Theory. Summing up, the EATCS Council will examine the future of Track C of ICALP in its coming meetings.

Mikkel Thorup also suggested that the submitted versions of the accepted ICALP papers should be posted on the conference web page as soon as they are accepted. This suggestion led to further interesting discussions. IMHO, it would certainly be beneficial to post the final versions of the accepted papers on the conference web site as soon as they arrive.

Thore Husfeldt suggested that the EATCS establish an SC for the conference, possibly independent of the council, and that the EATCS consider establishing a "fast track" for the publication of journal versions of the best ICALP papers. Regarding the first point, I informed the audience that the EATCS already has an ICALP Liaison Committee, but that it would be a good idea to give more power and responsibilities to it. That committee should also revise the current version of the guidelines for ICALP organizers, which are definitely out of date in the light of the new publication outlet for the proceedings and the new awards sponsored by the EATCS. I also informed the audience that the EATCS Council has been discussing the possible establishment of an open-access ournal of the association for some time.

Regarding awards, the audience suggested that the EATCS consider establishing an ICALP Test-of-Time Award. A young researcher even suggested that ICALP should have a best reviewer award.

I thank the attendees for their many suggestions and invite any reader of this post to send theirs to the president of the EATCS or as comments to this post. You are the life and blood of the association. Your input is always most welcome and the EATCS listens to you. We are here to serve.

Next the secretary and the treasurer of the EATCS delivered their annual reports. (The financial report is here and the report from the secretary is here.) We also thanked Dirk Janssens who left his post as treasurer of the EATCS after 27 years of sterling service to the association. We welcomed Jean-Francois Raskin as the new treasurer of the EATCS.

The rest of the general assembly was devoted to a report from the outgoing president (viz. me). I refer you to the slides for my presentation and to the EATCS Annual Report for the details. Here I will limit myself to saying that at the general assembly I announced the new leadership of our association for the coming two-year term. The new president of the EATCS will be Paul Spirakis (University of Liverpool and U. Patras). He will be supported by Leslie Ann Goldberg (University of Oxford), Antonin Kucera (Masaryk University) and Giuseppe Persiano (University of Salerno) as vice-presidents.

During the general assembly, Paul gave a short speech describing some if his objectives as president of the EATCS for the coming two years. The EATCS is in very good hands and I look forward to seeing its influence grow under its new leadership.

Let me close this report by asking my readers and the members of the TCS community at large the questions I posed to the colleagues who attended the general assembly:
  • What should the EATCS do for the TCS community?
  • What activities should the EATCS support (financially or otherwise)?
  • How can we make EATCS membership more attractive (especially among the younger generations)?
Any input you might have will be useful for the new leadership of the EATCS. Make your voice heard, so that the EATCS can serve the TCS community even better than it is already doing.

I thank all of you for the support I have received over the last four years in my role of president of the EATCS. It was a lot of work (to achieve probably very little), but I learned much from many of you. Thank you! You are the life and blood of the EATCS.

Monday, July 18, 2016

A peek at ICALP 2016 in Rome

ICALP 2016 took place last week in Rome from the 12th till the 15th of July. The conference, which brought ICALP to Italy for the fifth time, was well organized by Tiziana Calamoneri, Irene Finocchi, Nicola Galesi and Daniele Gorla, whom I thank for the effort they put into making ICALP 2016 a memorable event.

According to the data presented by Tiziana on behalf of the local organizers during the General Assembly of the EATCS held on Thursday, 14 July, ICALP 2016 had 239 registered participants, 74 of which were students. The USA was the country contributing the largest share of attendees (50), followed by France, the UK, Germany and Italy. Let me note, in passing, that I would have expected a larger number of participants from Italy, given the size of the Italian TCS community, the number of TCS researchers based in Rome and in neighbouring cities, and the ease with which Rome can be reached from most of the country. (Italy contributed 21 participants to the conference.)

ICALP 2016 featured four invited talks, which were delivered by Devavrat Shah (MIT, USA), Xavier Leroy (INRIA, France), Seffi Naor (Technion, Israel) and Marta Z. Kwiatkowska (Oxford, UK), as well presentations by the recipients of the Presburger Award, the Gödel Prize and the EATCS Award.

Devavrat Shah kicked off the conference on Monday, 12 July, by delivering a talk entitled Computing Choice. In his talk, Devavrat discussed algorithmic results relating to ranking, rank aggregation and personalized rankings associating intensity to rankings based on partial information resulting from a sparse set of comparisons. The talk, which was excellently paced and interesting, presented many results and I invite you to check Dev's work for the details.This work addresses computational challenges for decision making without a choice model, and offered a glimpse of the exciting possibilities for inter-disciplinary work across disciplines such as CS, EE, OR and Economics.

Xavier Leroy delivered the second invited talk, entitled Formally verifying a compiler: What does it mean exactly?, on Wednesday, 13 July. In his talk, Xavier discussed the context for, and the results of, the CompCert project, which investigates the formal verification of realistic compilers usable for critical embedded software. Such verified compilers come with a mathematical, machine-checked proof that the generated executable code behaves exactly as prescribed by the semantics of the source program. In this project, Coq is used both as a proof assistant and as a programming language.

In his talk, Xavier said that "Pure functional programming is the shortest path to writing and verifying software." He also asked and addressed two fundamental questions arising from this work and related ones:
  • Did we prove it (the compiler) right?
  • Did we prove the right thing? 
In particular, Xavier discussed the latter question in detail and argued that the social consensus underlying the acceptance of proofs in mathematics also plays a role in accepting proofs of software correctness. He also mentioned the "unreasonable effectiveness of labelled transition systems" in semantics and in supporting such correctness proofs.

Seffi Naor's talk took place on Thursday, 14 July, and was entitled Maximatization of submodular functions: Recent progress. Seffi stepped in at the last moment for Subhash Khot, who was unable to make the trip to Rome. On behalf of the EATCS and of the TCS community as a whole, I thank him for delivering an excellent talk at such a short notice.

Research on the topic of Seffi's talk started in  the 1950s-1960s and is now thriving. It has applications in the study of social welfare, economics/game theory, combinatorial optimization, machine learning and information theory. In his talk, Seffi first surveyed results on unconstrained maximization of non-monotone functions, with focus on approximation algorithms, and then presented results for the constrained maximization problem. I refer the readers to Seffi's papers and to this Wikipedia page for more information.

The last invited talk at ICALP 2016 was delivered by Marta Z. Kwiatkowska on Friday, 15 July. Marta's talk was entitled Model Checking and Strategy Synthesis for Stochastic Games: From Theory to Practice and is accompanied by a paper that is available here. Marta stated right at the start that, despite the success that model checking and synthesis techniques have had and are having, we have not found yet the right modelling abstractions for autonomous mobile agents such as robots and autonomous vehicles. Software for these vehicles is expected to behave reliably under uncertainty, and its analysis and synthesis require quantitative approaches to specification and verification. As Marta argued cogently in her talk, a game-theoretic point of view is fruitful in the study of such systems. Indeed, games of various kinds have played a fundamental role in the study of the synthesis of correct programs from specifications from the very beginning, and papers on game-theoretic models abound in Volume B conferences. (See the slides for this talk by Moshe Vardi for historical remarks and an overview of the game-theoretic approach to synthesis.) Rather than attempting to summarize Marta's talk, I strongly encourage you to read her accompanying paper, which beautifully summarizes her work on this topic and contains pointers to related literature.

The core of the scientific programme consisted of the papers that were selected for presentation by the PC chairs (Michael Mitzenmacher, Yuval Rabani and Davide Sangiorgi) and their PCs. Because of EATCS commitments, I could not attend as many talks as I would have liked, but all those I did manage to listen to were excellent both scientifically and from the point of view of the quality of the presentation. (For one of the talks, I even had to wear 3D glasses :-)) Thanks to the PC chairs and their PCs for doing a truly great job!

The award ceremony was held on Wednesday, 13 July, and saw the presentation of the EATCS Distinguished Dissertation Awards, of the Presburger Award to Young Scientists, of the Gödel Prize and of the EATCS Award. The event was a festive occasion and celebrated some of the outstanding members of the TCS community.

The EATCS Distinguished Dissertation Award Committee, consisting of Javier Esparza, Michal Feldman, Fedor Fomin,  Luke Ong and Giuseppe Persiano (chair), has selected the following three theses for the EATCS Distinguished Dissertation Award for 2015:
  • Radu Curticapean, The Simple, Little and Slow Things Count: On Parameterized Counting Complexity. Thesis work carried out at the Department of Computer Science at Saarland University, Saarbrücken, Germany. Supervisor: Markus Bläser.
  • Heng Guo. Complexity Classification of Exact and Approximate Counting Problems. Thesis work carried out at the Department: of Computer Sciences in the University of Wisconsin-Madison. Advisor: Jin-Yi Cai,
  • Georg Zetzsche. Monoids as storage mechanisms. Thesis work carried out at the Department: of Computer Science at University of Kaiserslautern. Supervisor:  Roland Meyer. 
The award committee received an impressive set of submissions in terms of quality. The three selected theses are outstanding.

The Presburger Award was presented to  Mark Braverman (Princeton University, USA). The Gödel Prize went to Stephen Brookes and Peter O'Hearn for their invention of concurrent separation logic, and the EATCS Award was given to Dexter Kozen. The presentation of each of these three awards was accompanied by an excellent talk by the award recipient(s). As I mentioned during the award ceremony, this might very well be the first time that the Gödel Prize is mentioned in a piece in the New Yorker.

The award session was extremely well attended and preceded a short bus tour in Rome and a social dinner in a popular restaurant in Trastevere.

The annual General Assembly of the EATCS took place on Thursday, 14 July. I'll report on it elsewhere. Here I will limit myself to saying that, at the General Assembly, I formally stepped down as president of the EATCS after two terms of service (four years). The new president of the EATCS will be Paul Spirakis (University of Liverpool and U. Patras). He will be supported by Leslie Ann Goldberg (University of Oxford), Antonin Kucera (Masaryk University) and Giuseppe Persiano (University of Salerno) as vice-presidents. At ICALP 2016 in Rome, Dirk Janssens also left his post as treasurer of the EATCS after 27 years of sterling service. Jean-Francois Raskin kindly accepted to serve as the new treasurer of our association. The association is very grateful to the above-mentioned colleagues for their willingness to serve and to Dirk for his outstanding service over such a long time. I know that the EATCS community will support the members of the new leadership  in their work, just like they helped me during the last four years.

If you were at ICALP in Rome and you have any comment, suggestion or criticism, please post them as comments. I'll make sure that they reach the leadership of the EATCS. We are always working on improving an already very successful conference that does its best to provide a bird's eye view of TCS as a whole.

Monday, July 04, 2016

Call for guest bloggers at ICALP 2016

I would like to have some blog coverage for ICALP 2016. If you are attending the conference in Rome and you are interested in guest blogging, drop me a line. Ideally, I would like to have a guest blogger for each of the tracks in the conference. You are, of course, also most welcome to blog about the five invited talks, the award ceremony, the general assembly and any other aspect of the conference.

I'll try to write something myself, but the more the merrier!

Tuesday, June 21, 2016

EATCS Bulletin Issue 119 is available online

The June 2016 issue of the Bulletin of the EATCS is now available on line. If you prefer, you can download a pdf with the printed version of the Bulletin. As usual, thanks to the support of the members of the EATCS, the Bulletin is open access.

This issue of the Bulletin  features the following columns:
Some of you might also be interested in advice to young researchers from Michael Fellows and other Fellows of the EATCS, and in interviews with the recipients of the Gödel Prize 2016 and of the first Alonzo Church Award.

Thanks to Kazuo Iwama, the editor in chief of the Bulletin, and the EATCS Secretary Office for their work on another excellent issue of the Bulletin.

Monday, June 06, 2016

One PhD or post-doctoral position at the School of Computer Science, Reykjavik University

Theoretical Foundations for Monitorability

School of Computer Science, Reykjavik University
One PhD or Postdoctoral Position

Applications are invited for one PhD or postdoctoral position at the School of Computer Science, Reykjavik University.  The position is part of a research project funded by the Icelandic Research Fund, under the direction of Luca Aceto (Reykjavik University), Adrian Francalanza (University of Malta) and Anna Ingolfsdottir (Reykjavik University). The general aim of the project is to develop further the theoretical foundations of monitorability for fragments of variants of Hennessy-Milner logic with recursion/modal mu-calculus.

The project work will build on the RV 2015 paper by the co-proposers (, and on the experience developed during their previous work on runtime verification and on the tool detectEr ( The goals of the project will be:

  • to explore more stringent conditions for detection than the ones considered in the RV 2015 paper and study whether this has any effect on the monitorable subset of the logic;
  • to investigate the monitorability of the logic with respect
    to instrumentation set-ups other than the one used in the RV 2015 paper;
  • to extend our results from the RV 2015 paper to the setting of real-time systems, modelled as timed automata, and to a real-time variant of Hennessy-Milner Logic with recursion;
  • to understand how existing notions of monitorability relate to the one formulated in the RV 2015 paper, thereby consolidating disparate concepts of monitorability;
  • to investigate extensions to monitorability that incorporate notions
    of enforceability; and
  • to apply the results of the theoretical work in the construction of a prototype software tool for the runtime analysis of systems.

The successful candidates will benefit from, and contribute to, the research environment at the Icelandic Centre of Excellence in Theoretical Computer Science (ICE-TCS). For information about ICE-TCS and its activities, see

Moreover, she/he will visit Adrian Francalanza's group at the University of Malta during the project work and will benefit from the research experience on runtime verification within that group.

Qualification requirements

Applicants for the PhD fellowship should have an MSc degree in Computer Science, or closely related fields. Some background in concurrency theory and mathematical competence are desirable.

Applicants for the postdoctoral position should have, or be about to hold, a PhD degree in Computer Science or closely related fields. Previous knowledge of at least one of concurrency theory, process calculi, (structural) operational semantics and logic in computer science is highly desirable.

The PhD position provides a stipend of 290,000 ISK (roughly 2080 € at the current exchange rate) per month before taxes, for three years, starting as early as possible.

The wage for the postdoctoral position is 400,000 ISK (roughly 2870  € at the present exchange rate) per month before taxes. The position is for one year, starting on September 1, 2016 (later starting dates are possible), and is renewable for another year, based on good performance and mutual satisfaction.

Application details

Interested applicants should send their CV, including a list of publications, in PDF to all addresses below, together with a statement outlining their suitability for the project and the names of at least two referees.

Luca Aceto

Adrian Francalanza

Anna Ingolfsdottir
We will start reviewing applications as soon as they arrive, and will continue to accept applications until the position is filled. However, we strongly encourage interested applicants to send in their applications as soon as possible.