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 (https://en.ru.is/scs/). 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

Thursday, November 16, 2017

Two and a half months at the Gran Sasso Science Institute

About two and a half months have passed since I started working at the Gran Sasso Science Institute (GSSI). I still have much to learn about the functioning of the Italian university system (and even of the GSSI), and it is already clear that there will be many of its aspects that I will probably never learn. However, my impression so far is that the level of bureaucracy in Italy is definitely higher than that in the countries where I have previously worked.

On page 88 of this interesting article, the historian Rogers Hollingsworth writes:
"One of the factors influencing creativity at the level of the nation state is the institutional environment in which scientists conduct research. I code scientific institutional environments as ranging from weak to strong. Weak institutional environments exert only modest influence (1) on the appointment of scientific personnel of research organizations, (2) in determining whether a particular scientific discipline will exist in a research organization, (3) over the level of funding for research organizations, (4) in prescribing the level of training necessary for a scientific appointment (e.g., the habilitation), and (5) over scientific entrepreneurship (e.g., the norms of individualism that socialize young people to undertake high-risk research projects). Strong institutional environments are at the opposite end of the continuum on each of these characteristics. Weak institutional environments have tended to facilitate greater scientific creativity in a society than strong institutional environments..."
(The emphasis is mine.) According to the above description, the Italian scientific institutional environment can only be classified as strong, for good or for worse. Fortunately, the GSSI is a centre for advanced studies and an international PhD school. Even though it has to follow the Italian law, with all its quirks, it is more nimble and less rigid  than the average Italian university. Moreover, most of the bureaucracy is hidden to the junior members of our faculty, such as the assistant professors, who can largely concentrate on the scientific work.
I have always appreciated the work that Italian researchers have been carrying out over the years, but what I have seen so far has increased my esteem for them even more. In spite of the extremely rigid system within which they are forced to operate, they manage to be productive and to maintain a strong commitment to their research work, achieving a high level of scientific production, both in quality and in quantity. The GSSI hosts a number of top-class academics in its four fields of research (computer science, mathematics, physics and social sciences) and this creates a stimulating environment for faculty and students alike.

The computer science group at the GSSI is still too small, but it seems to me that it punches well above its weight. Its members are very dedicated and have done an amazing job since the beginning of the GSSI adventure. (It was a humbling learning experience for me to present their achievements to the Scientific Advisory Board of the GSSI last Monday.)

It is clear that our group needs to grow, but we want to do so well. If you work in one of the research areas that we cover, at their intersection or in sister ones, and you think you'd be interested in working in L'Aquila with our faculty, do drop one of us a line, sending your CV and an expression of interest. We are keen to recruit strong researchers at all levels who can help us build the best international research centre in computer science we can. I can vouch that the computer science group at the GSSI provides young researchers with early-career autonomy in a nurturing environment, which isn't very common in Italy (as far as I know), and with the opportunity to become involved in the supervision of doctoral students. There are also resources for inviting collaborators and organizing thematic events, amongst other things.

It will be interesting to see how the computer science group will develop at the GSSI over the coming year. 

Friday, September 29, 2017

Reykjavik University: A THE top-500 university

Reykjavik University is in the top 500 universities in the world, according to the THE rankings. See here for details about my Icelandic workplace.

This is the first time RU appears on the list, which is an excellent result for a young and specialized university.

Even though all rankings should be taken with a pinch of salt, this is a remarkable achievement for a small university in a tiny country. Congratulations to my colleagues at Reykjavik University, who made this achievement possible with their work in research, teaching and service to the academic community.

Friday, September 01, 2017

Computer Science at the Gran Sasso Science Institute

I recently advertised a call for four PhD positions in computer science at the Gran Sasso Science Institute (GSSI) in L'Aquila, Italy. That post included a link to a web site with some information about the GSSI. However, some potential applicants, and colleagues in general, might be interested in knowing more about the CS group in this new institute, without having to browse through a series of web pages. I therefore decided to collect some relevant information on CS@GSSI in this blog post in the form of a FAQ, hoping it may be of help to students and computer science researchers who might wish to consider working at the GSSI.

  1. What is the GSSI? The GSSI is a recently established university in Italy. It is an institute for advanced study and an international PhD school, having English as its official language. It is located in L'Aquila, Italy, in the beautiful Abruzzo region. It focuses on astroparticle physics, computer science, mathematics and urban studies.
  2. What areas of CS are covered at the GSSI? Information on research at CS@GSSI may be found here. In short, CS@GSSI is based on three main areas, namely the algorithmic study of computer and social networks (as covered, for instance, by ICALP Track A and Track C), specification and analysis of reactive systems, and software engineering techniques for building usable and easily maintainable distributed applications. 
  3. Who works at CS@GSSI? CS@GSSI is still in its infancy and has ambitious growth plans in the short to medium term. In the area of algorithms, Michele Flammini, Gianlorenzo D’Angelo (recipient of the “Best Italian Young Researcher in Theoretical Computer Science” award for 2016 of the Italian Chapter of the European Association for Theoretical Computer Science) and Mattia D’Emidio have been the first researchers working at GSSI. Rocco De Nicola (whose main affiliation is at IMT Lucca) has been the director of the CS programme and has spearheaded the work in formal methods, together with Omar Inverso. I joined the GSSI as a professor today. Work in software engineering has been carried out by Ludovico Iovino, Catia Trubiani and people in the high-profile research group in SE at the University of L'Aquila led by Paola Inverardi. Former GSSI postdoc Ivano Malavolta is now an assistant professor in Data-Driven SE at VU Amsterdam, and is jointly supervising some students at GSSI.
  4. Apart from the faculty at GSSI, with whom can PhD students interact at CS@GSSI? CS@GSSI has a vibrant guest lecturer programme, with frequent visits by top-class researchers from all over the world, as well as affiliated faculty. See here for the details. (Look for "Scientific collaborators" and "Lecturers from other institutions".)
  5. How is the scientific environment at CS@GSSI? The group runs a seminar series and has already hosted conferences and workshops. See here for some information. It will soon organize SAGT 2017 at GSSI. Other events are in the works.
  6. How many PhD students in CS are there? What do the graduates do after their PhD? CS@GSSI hosts about 30 PhD students at all times. You can see the list of current students here. The institute is only about three years old, so only some of the first batch of students have graduated or are about to do so. Of those, all of them have found postdoctoral positions at institutions in Italy. Two GSSI students who just submitted their theses will join Jukka Suomela's group at Aalto University from January 2018.
If you have any further questions, please post a comment to this post, so that I can keep the FAQ up to date and as informative as possible.

Wednesday, August 30, 2017

Call for GSSI PhD Applications in Computer Science now open

Encourage students interested in TCS (both volume A and volume B) and Software Engineering to apply for these four PhD positions in Computer Science at the Gran Sasso Science Institute! The deadline is the 18th of September.

The Gran Sasso Science Institute (GSSI) offers 4 PhD positions in Computer Science for the academic year 2017/18.

The fellowships are awarded for three years and their yearly amount is € 16,159.91 gross. All PhD students have free accommodation at the GSSI facilities and use of the canteen.

The application must be submitted through the online form available at www.gssi.it/phd/ by September 18, 2017 at 18.00 (Italian time zone).

For more information, please consult the Call for Applications at www.gssi.it/phd/ or write an email to info@gssi.it or call +39 0862 4280262.

Tuesday, August 08, 2017

Proofs of the Dichotomy Conjecture (guest post by Petar Marković)

I have received the following contribution by Petar Marković, who summarizes recent developments related to the three proofs of the Dichotomy Conjecture that have been proposed since the start of the year and provides an overview of the proofs by Bulatov and Zhuk. The first part of the post is based on a comment Petar posted here. The second is more technical and provides an overview of the proofs by Bulatov and Zhuk, which will be presented at FOCS 2017. I hope that Petar's overview will entice some experts who have not read those proofs to do so and will help them  as they delve into the technicalities. Thanks to Petar for taking the time to summarize his understanding of the proofs with the community. 

Addendum dated 12 December 2017: Bulatov and Zhuk have shated the best paper awards at FOCS 2017 with Ola Svensson and Jakub Tarnawski. See here. Thanks to Lance Fortnow for sharing this piece of news with me.

Status of the three proposed proofs for the Dichotomy Conjecture

As several people in the community have been aware of, the proof of Feder, Kinne and Rafiey has been suspect since it appeared. The parts where they are unclear, or wave hands over details, are precisely the parts where, in the opinion of several experts, the main difficulty was. Unfortunately, this has led to a counterexample and the retraction by Feder, Kinne and Rafiey of the claim they have solved the Dichotomy Conjecture. Their retraction can be found in the comments which replace the abstract of the fourth and most current version of their paper, see https://arxiv.org/abs/1701.02409.

More concretely, it was pointed out in private conversation of several experts that their proof fails on Miklós Maróti's ‘tree-on-Mal’cev’ kind of problems, when they are eliminating what they call `non-minority cases'.

Incidentally, ‘tree-on-Mal’cev’ is not some obscure class of CSPs. As people who are reading it will surely agree, generalizing Maroti's result to 'semilattice-on-Mal’cev’ is the cornerstone of Andrei Bulatov's proof of the Dichotomy Conjecture, the rest is a (very technical and difficult) generalization of the ideas which solve this special case. Even though Feder, Kinne and Rafiey were working only on digraph templates, while ‘tree-on-Mal’cev’ does not specify the relations, just the polymorphisms, the construction by Bulin, Delić, Jackson and Niven, which improves on the original one by Feder and Vardi, reduces a general template to a digraph one, while preserving not only the complexity but also most polymorphisms. So Feder, Kinne and Rafiey's algorithm should have been able to solve those ‘tree-on-Mal’cev’ templates.

Ross Willard, who also was among the experts involved in the initial conversation in January, took the trouble to actually construct digraph CSPs out of the 'tree-on-Mal'cev' CSPs. He constructed out of a tree-on-Mal’cev template a digraph template which contradicts the claim in Feder, Kinne and Rafiey paper that certain situation in the digraphs allows the domain of a variable, and thus the multi-sorted instance, to be reduced by a vertex. This contradicts the whole philosophy of their approach, creating a barrier where they can't proceed with reductions. He emailed the authors of Feder/Kinne/Rafiey his counterexample and, working together, they simultaneously published the retraction, while he published his counterexample on arxiv. The counterexample is available at https://arxiv.org/abs/1707.09440.

On the flip side, at a fairly large conference in June in Novi Sad, Serbia, both Bulatov and Dmitriy Zhuk had plenary talks. After the afternoon in which they exposed their proofs of the Dichotomy Conjecture to a general audience, a special event was organized which lasted almost three hours. The idea was that each would discuss minutiae of their proofs and answer challenges from present experts. In the audience there were about a dozen people who may safely be called experts on the algebraic approach to CSP and most have read in detail large parts of both proofs. There were many interruptions and serious questions were asked, but both proofs survived all challenges unscathed. My degree of confidence after this event in both Bulatov's and Zhuk's proofs is very high, well over 90%, and the odds that both are wrong are really small.

Overview of the proofs by Bulatov and Zhuk

The proof by Bulatov has several ingredients: 
1. his own colored graph theory of algebras which he has been developing for the past decade or so and which he additionally improved on for this paper,
2.  a new centralizer notion which is similar to the classical one from 1980’s Freese and McKenzie book, but this one involves binary polynomials instead of terms of arbitrary arity,
3. a connectedness notion, dubbed ‘coherent sets’, between domains of various variables, somewhat reminiscent of what McKenzie and I called ‘strands’ in an unpublished paper about semilattice-over-Mal’cev CSPs, but much more complicated
4. Maróti’s reduction which solves one of his reduced cases. This reduction uses polynomials of the polymorphism algebra (operations created from polymorphisms by fixing some variables as constants) to find a related smaller CSP instance, which either has no solution, in which case the original one doesn’t have a solution, or has a solution, in which case that solution shows how to reduce the original instance to a smaller one,
5. a crazy amount of consistency which assures that another of his three reduced cases must have a solution if it is nonempty,
6. the old few subpowers algorithm in his third reduced case, and finally
7. a massive induction which lowers the location of congruence covers modulo which coherent sets are considered, working simultaneously through various congruence lattices of variable domains. When they can appear only at the bottom then the reduced cases 4., 5. and 6. occur. It is this last part which is the hardest and requires most scrutiny. The rest is mostly clear to experts (personally, I would say I am sure the rest is correct).

I understand Zhuk’s proof much less, but the main ingredient is his structure theory of relations. He subjects the constraint relations to several extreme conditions he invented (and can assume after some effort). Next, he also works down the congruence lattices of various domains of variables. There are three types of reductions he uses to reduce to an instance which satisfies all these assumptions. When the congruences have also been subjected to extreme assumptions, then his theory of relations claims that each lower cover of the current congruence in each domain of variable is a Mal’cev cover. He can solve the Mal’cev problem, which is pretty much a system of linear equations, and arrive at the solution space to the factor problem. Also, he can test whether this is the same space as the space of all solutions to the initial instance, factored. This is easy, he just selects one solution of the factored problem and uses its classes as new domains of variables. They are smaller than the original ones so inductively he can solve it. If it has a solution, he found a solution to the original instance. If not, he works on finding a new constraint which does not affect the solution space to the original instance, but reduces the dimension of the solution space to the factor problem. (Finding this constraint relies on his structure theory and on other reductions, and is probably the hardest part of his proof.)

There is a circular nature to Zhuk’s proof which uses all four types of reductions in previous cases to prove the one he is currently applying. This is an idea similar to ‘simultaneous induction’ in Adian and Novikov’s proof of Burnside conjecture which was later much used in group theory.

The very high-level bird-eye view is that Bulatov reduces everything to consistency checking or few subpowers (when there are no ‘semilattice edges’), Zhuk reduces in a circular way, but Mal’cev is what he seems to end at, while Feder, Kinne and Rafiey also reduce everything to Mal’cev, but have a problem in eliminating some semilattice covers. Since the absence of semilattice covers is the same as having few subpowers, the missing part in Feder, Kinne and Rafiey is serious.

Monday, July 17, 2017

Why you should join the EATCS and convince your colleagues to do so too

Let me state at the outset that, as former president of the EATCS, I am somewhat biased on the matter I cover in this post. However, I do believe that what I write below is based on facts rather than bias. I hope that you will draw your own conclusions and join a scientific associations that provides sterling support for theoretical computer science as a whole.

The first question I am typically asked when I encourage a colleague to join the EATCS is  "What is in it for me?" This question is natural and easy to answer (see here), but I believe that it is the wrong question to ask. As someone who has lived a fair number of years in sunny, socialist Scandinavia and a closely related country, I have grown into thinking that a better question would be "What's in it for the TCS community?" To my mind, the answer to this second question is even clearer.

The EATCS is a scientific association that, compatibly with its limited resources, does much for TCS.
  • Its Bulletin has been open access for over ten years. Anyone can read it for free, unlike many other bulletins and newsletters that are only available to members of professional societies. This is made possible by the support of the EATCS members for the benefit of everyone. 
  • The proceedings of ICALP have been open access since last year. The association lost money by deciding to go for open-access proceedings, but its council felt that the time had come to serve the community in this way. 
  • The EATCS provides financial support to conferences and young researcher schools, and sponsors prizes and awards that put TCS research in the limelight. When I was the president of the EATCS, I was surprised to receive sponsorship requests from the organizers of conferences that were officially "sponsored" by incomparably larger and richer professional societies. The EATCS provided a small financial sponsorship to some of those events, as part of its mission. Now I have a better idea of why those conferences were asking for EATCS sponsorship. 
  • Conferences that collect EATCS membership fees receive some of those fees back from the association. I have come to understand that this is not the case for other professional societies. 
I could go on, but this short list should be sufficient to help you make up your mind and I do not want this post to turn into a rant. The bottom line is that by joining the EATCS, you will support TCS for a mere 30 € per year (two years if you are a student). Do you need more reasons to join and help the community?

If you have any questions or doubts, air them as comments to this blog post. 

Sunday, July 09, 2017

Call for guest bloggers at ICALP 2017

I would like to have some blog coverage for ICALP 2017. If you are attending the conference in Warsaw 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 invited talks, the award ceremony, the general assembly, the affiliated workshops and any other aspect of the conference you fancy. 

Unfortunately, I cannot attend ICALP this year, so there won't be any reporting from me. 


Thursday, June 29, 2017

Tenure-track assistant professorship (cyber security) at IMT Lucca

I have been asked to distribute this job announcement. For what it is worth, I strongly recommend IMT Lucca, an ambitious doctoral school and centre of advanced studies, and Lucca is a wonderful place to live.

IMT School for Advanced Studies Lucca invites applications for a tenure-track assistant professorship in Computer Science
(Ricercatore a Tempo Determinato Tipo B, RTD-B - INF/01).

We particularly welcome candidates with experience or willingness to work in the area of cyber security broadly construed, ideally complementing IMT’s current strengths. Topics of interest include (but are not limited to):
- access control;
- cryptocurrencies;
- formal verification of security protocols;
- security requirements elicitation;
- web security;
- security of “Internet of Things”.

The successful candidate is expected to publish in first-class journals and in the proceedings of top conferences in computer security. Moreover, she/he is expected to establish links with local companies and institutions that have shown high interest in cybersecurity, and to apply for national and international research funding.

According to Italian law, RTD-B assistant professors will be employed for three years, during which they are required to secure a habilitation (ASN) from an independent national evaluation committee in order to obtain tenure at the associate professor level. Applicants to ASN are evaluated based on various indicators of scientific quality and leadership such as bibliometrics, research grants, invited talks, and best-paper awards.

IMT is one of Italy’s six schools of excellence for postgraduate education, ranked first in the last national research assessment exercise. IMT researchers are expected to contribute to the teaching and supervision of PhD students, admitted to the School through a selective international competition. The working language is English.

The salary will be determined on a personal basis within pay grades defined as per Italian legislation. The indicative starting gross salary for an RTD-B assistant professor is € 34,898. Net income may vary depending on income taxes, local taxes, retirement plan, health care deduction and tax exemptions. New employees who have worked in research-based positions abroad for the previous two years may be eligible for a substantial tax rebate for the first three fiscal years of employment.

The online application form is available at
!!!!!Deadline July 27th, 2017 - Italian midday!!!!!

Wednesday, June 28, 2017

Ten years of the European Research Council: A View from TCS

The European Research Council (ERC) turned ten this spring. This event has been celebrated in Brussels and in many European countries with thematic events, highlighting success stories in research related to the ERC and examining possible future developments for this remarkable funding agency. Helga Nowotny, the first President of the ERC, has written an editorial in Science looking at the future of the ERC. In that editorial she summarized the first ten years by saying that, since its inception, through international competition, the ERC has awarded grants amounting to over 12 billion euros to about 7,000 researchers in Europe. Two- thirds of those awards went to young scientists with 2 to 12 years of experience after receiving their PhD.

I held a small opinion poll within the theoretical computer science (TCS) community to try and find out what TCS researchers think of the first ten years of the ERC and to see how this, undoubtedly very successful, funding agency can be improved. To this end, I wrote to 26 colleagues in TCS, who cover a fairly broad spectrum of topics within TCS research and have a diverse geographical distribution. Some of those colleagues have received at least one ERC grant at various stages of their careers, but some haven’t so far.

I received 21 replies, so my emailing effort had a good 80.7% success rate. I thank the colleagues who took time from their busy schedules to reply to my questions.

In case anyone is interested, I penned a contribution to the October issue of the Bulletin of the EATCS summarizing my findings. You can read it here.

Wednesday, June 14, 2017

Interview with Alexandra Silva, Recipient of the 2017 Presburger Award

The European Association for Theoretical Computer Science (EATCS) established the Presburger Award in 2010. The award is presented each year at ICALP "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 2017 Presburger Committee, consisting of Marta Kwiatkowska (chair), Stephan Kreutzer and Jukka Suomela, has selected Alexandra Silva (Senior Lecturer at University College London, UK) as recipient of the 2017 EATCS Presburger Award for young scientists. To my mind, this is a wonderful choice. Alexandra Silva is one of the brightest rising stars within our research community and, in a very short period of time, has established herself as a research leader and a mentor for young researchers, who somehow also finds the time to serve the theoretical-computer-science community in a variety of roles.

I interviewed Alexandra Silva (abbreviated to AS in what follows) via email and present her answers to my questions in what follows. I hope that the readers of the Bulletin of the EATCS will enjoy reading the text of the interview and will find it as interesting as I did. Most importantly, I trust that young researchers and students in (theoretical) computer science will be inspired by Alexandra's example to pursue a career in our exciting field of science.

LA: Alexandra,  first of all, congratulations for the 2017 Presburger Award! I wanted to start by asking you about your background and when you became
interested in computer science.  When did you decide to pursue a PhD and a career in academia? Is there anyone who played an important role in that decision?

AS: I wanted to study mathematics, but my brother convinced me I should do a double bachelor in maths and CS because otherwise I would not get a job :-) I did a Math and CS degree at Universidade do Minho  (Braga, Portugal) and fell in love with the foundations of CS. I decided to pursue a PhD after a very happy research project at the end of my degree supervised by Joost Visser and Jose Nuno Oliveira. I worked very closely with Joost for 6 months and he was a great inspiration in my career and taught me the basic principles of research. Another person who was instrumental was Luis Barbosa: he motivated me to go abroad for a PhD and to ask Jan Rutten to be my advisor.

LA: So far, you have studied and worked in Portugal, the Netherlands and the UK, and have collaborated with researchers in Germany and the US, amongst others. How important has this variety of experiences been for your career development? Do you prefer to work alone or to collaborate with other people?

AS: Working in different countries and being exposed to different cultures has made me a more flexible and resilient person.  This has been very important in my career, also to help me deal with all the rejected papers and grant proposals! :-) I am happy to meet new people and discuss research. When I am excited about a new idea I like to share it with my colleagues and discuss ways to improve it!

LA: Could you tell our readers briefly what your main research interests are today?

AS: These days I am very keen on applications of automata learning in verification. Frits Vaandrager planted the seed in 2011 when I joined Nijmegen and 4 years later I really saw the light and since then have been very excited on working in understanding existing learning algorithms and improving them, using a categorical perspective on their correctness proofs. I am currently exploring connections with my other passion -- Kleene algebra and extensions thereof -- and looking at learning NetKAT specifications from networks. 

LA: These days you are managing a fairly large research group.  Have you found it difficult to become the leader of a group, with the responsibility of managing substantial research grants and of making sure that the young researchers in the group thrive and produce the best work they can? Is there any specific strategy you adopt in managing your group?

AS: I find it very exciting but at the same time the responsibility does overwhelm me at times. I see these super bright young minds and would like to help all of them thrive, in ways other people have helped me in my career. My current strategy is to make sure they know I am always available to talk and help but more importantly I want them to realise they are part of a team and support can come from anyone in that team. We have a slack channel that is very active and in which all issues are discussed -- from completeness of Kleene Algebra to how you can trick image recognition software to think a puppy is fried chicken (credits to Joshua Moerman!).

LA:  I know that you have a strong interest in gender issues and in increasing the number of women in computer science and their visibility within the community. What has been your experience as a young woman in TCS? Do you have any advice to offer to the community in order to attract and retain more talented female students? Did you have any female role model and how important do you think they are in general?

AS: I was very lucky at the beginning of my career and throughout my PhD and post-doc I never felt there was any problem. This was in part due to my advisors -- Jan Rutten, Marcello Bonsangue, and Dexter Kozen -- who were real mentors throughout the years and always made me feel welcome in the research environment of their groups. It was when I became a faculty member that I felt animosity from several male colleagues. One told me that I only got my first faculty job because I was a woman. That day I truly thought it was the end of my career. I survived that incident and the many that followed but it did leave marks and a strong will to avoid others having to go through the same. When Prakash [Panangaden] invited me to join the SIGLOG executive board I saw an opportunity to do something for the community and pushed that we implement anti-harassment policies in SIGLOG conferences and try to foster a welcoming environment for everyone. I am not sure I have any good advice on how to attract female students -- I think as a community we need to strive to create more welcoming environments and start new trends in which being a woman in TCS becomes a normal thing! Catuscia Palamidessi and Marta Kwiatkowska are great female role models and have inspired me at various points me in my career. I have also had many male role models, including yourself, for which I am very grateful!

LA: Finally, you were one of the prime movers in establishing the Logic Mentoring Workshop at LICS. is there any advice you'd give a computer science student with an interest in carrying out research in TCS and working in academia?

AS: Whatever topic you decide to work on, the most important thing is to be excited about it. Happier research is better research, in my opinion. Also, the topic you choose today will not define you in the future: that is the beauty of working in academia, one can change research topic during the years! From a more practical perspective, it is important to have mentors and role models that will help you make the right decisions at important turning points of your career.

Monday, June 12, 2017

Has the Feder-Vardi dichotomy conjecture been proved? (Take 3)

In this post and this one,, I mentioned a paper by Arash Rafiey, Jeff Kinne and Tomás Feder and one by  Andrei Bulatov, claiming a solution to the long-standing Feder-Vardi dichotomy conjecture. Today Moshe Vardi pointed out to me this paper by Dmitriy Zhuk that offers a third proof of that conjecture.

At this point, I think that one can safely say that the dichotomy conjecture is true. Indeed, I find it hard to believe that all the three proofs contain mistakes that cannot be patched. As I wrote in my earlier posts on this matter, I hope all the proofs will be found to be correct by the community and that the techniques used in those articles will find application in other contexts.

Congratulations to the authors of those papers!

Saturday, May 27, 2017

Best paper awards at ICALP 2017

The following papers will receive the best paper awards at ICALP 2017 (source: http://icalp17.mimuw.edu.pl/?page_id=370):

  • Best Track A Paper: A. Björklund, P. Kaski and I. Koutis.  Directed Hamiltonicity and Out-Branchings via Generalized Laplacians. 
  • Best Track A Student Paper: E. Lee. Improved Hardness for Cut, Interdiction, and Firefighter Problems. 
  • Best Track B Paper: M. Benedikt, P. Bourhis and M. Vanden Boom. Characterizing Definability in Decidable Fixpoint Logics. 
  • Best Track B Student Paper: F. Reiter. Asynchronous Distributed Automata: A Characterization of the Modal Mu-Fragment.
  • Best Track C Paper: E. I. Ásgeirsson, M. M. Halldorsson and T. Tonoyan. Universal Framework for Wireless Scheduling Problems.
Congratulations to all the award recipients!

It's been another good year for Nordic TCS (best papers at tracks A and C). Of course, we at ICE-TCS are particularly pleased for the Track C best paper award to our ICE-TCS colleagues Eyjólfur Ingi Ásgeirsson, Magnús Már Halldórsson and Tigran Tonoyan. Way to go!

Friday, May 05, 2017

2017 Alonzo Church Award announcement

Gordon Plotkin has kindly shared the 2017 Alonzo Church Award announcement with me. I am happy to post it here and hope that readers of this blog will be enticed to learn about this truly fundamental contribution to theoretical computer science.

The 2017 Alonzo Church Award for Outstanding Contributions to Logic and Computation is 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, thereby fundamentally revolutionising the field of programming language semantics, and for the applied impact of these models. Their contributions appeared in three papers:
  • S. Abramsky, R. Jagadeesan, and P. Malacaria. Full Abstraction for PCF. Information and Computation, Vol. 163, No. 2, pp. 409-470, 2000. 
  • J.M.E. Hyland and C.-H.L. Ong. On Full Abstraction for PCF: I, II, and III. Information and Computation, Vol. 163, No. 2, pp. 285-408, 2000. 
  • H. Nickau. Hereditarily sequential functionals. Proc. Symp. Logical Foundations of Computer Science: Logic at St. Petersburg (eds. A. Nerode and Yu.V. Matiyasevich), Lecture Notes in Computer Science, Vol. 813, pp. 253-264. Springer-Verlag, 1994. 
Description of the Contribution 

These papers made two fundamental contributions to our understanding of programming languages and logic. First, they provided signi ficant insight into the longstanding and fundamental "full abstraction problem" for the paradigmatic higher-order language PCF by giving a compositional semantic account of sequentiality, via an elegant cartesian-closed category of games and strategies. In the mid-1970s Milner posed the full-abstraction problem for PCF and Plotkin showed the difficulty of the problem, which essentially lies in the fact that the standard Scott-Strachey model permits non-sequential functions, although PCF itself is sequential.

The papers constructed models for PCF from games, leading to the first fully abstract models of PCF whose construction made no reference to the syntax of PCF. The elements of the models are strategies for certain kinds of interactive dialogues between two players (or between system and environment). These dialogue games are required to follow certain conventions concerning when questions are posed or answered; these conventions reflect constraints on the information available to the players of the game. The papers give new insight into the fundamental work in higher-type recursion theory of such logicians as Kleene, Gandy, Normann, and Hyland.

Second, and perhaps more importantly, game semantics has provided a new framework for the semantics of programming languages. Games can be used as a flexible and modular modelling tool, as a wide variety of programming language features can be understood as corresponding to different restrictions placed on allowed strategies. Thus there are fully abstract games models for call-by-value and call-by name languages; for languages with state, with control, with references, with exceptions, with nondeterminism, and with probability; and for concurrent and mobile process languages. In this way, game semantics has changed the landscape of programming language semantics by giving a unified view of the denotational universes of many different languages. This is a remarkable achievement that was not previously thought to be within reach.

Techniques developed in game semantics have found their way into a wide variety of applications. For example, they have provided tools for the verification of a range of computational systems, such as reactive systems of timed and hybrid automata, higher-order and mobile processes, and model-checking higher-order programs. There has also been significant influence on other areas, for example, static program analysis, type systems, resource-sensitive compilation, and compiler certification. All of these developments can be traced from the initial work of Abramsky, Jagadeesan and Malacaria, of Hyland and Ong, and of Nickau.

The 2017 award will be presented at the 26th Computer Science Logic (CSL) Conference, the annual meeting of the European Association for Computer Science Logic. This will be held August 20th{24th, 2017, at Stockholm University, Sweden.

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 Godel Society (KGS). The award is for an outstanding contribution represented by a paper, or small group of papers, within the past 25 years; this is the second such award. The 2017 Award Committee consisted of Catuscia Palamidessi, Gordon Plotkin (chair), Natarajan Shankar, and Moshe Vardi.

Thursday, May 04, 2017

Call for participation: LearnAut at LICS 2017

The organizers of the Learning and Automata (LearnAut)  workshop, which is co-located with LICS 2017, have asked me to distribute the appended call for participation. 

The full list of workshops is available at

The early registration deadline is tomorrow
Please distribute this call to your students and research collaborators, as you see fit.



Learning and Automata (LearnAut) — LICS 2017 Workshop
June 19, Reykjavik (Iceland)
Early registration: May 5th

Grammatical Inference studies machine learning algorithms for classical recursive models of computations like automata and grammars. The expressive power of these models and the complexity of associated computational problems are a major research topic within theoretical computer science. This workshop aims at offering a favorable place for dialogue and at generating discussions between researchers from these two communities.

The following papers have been accepted for oral presentation:

  • Enes Avcu, Chihiro Shibata and Jeffrey Heinz: Subregular Complexity and Deep Learning
  • Alexander Clark: Strong learning of Probabilistic Context-Free Grammars from Strings
  • Nathanaël Fijalkow: Bisimulation on Distributions for Markov Decision Processes
  • Oded Maler and Irini-Eleftheria Mens: On Learning Symbolic Automata over Boolean Alphabets
  • Ariadna Quattoni, Xavier Carreras and Matthias Gallé. Scalable Spectral Learning of Automata through Maximum Matching
  • Rick Smetsers: Grammatical Inference as a Satisfiability Modulo Theories Problem

In addition, the papers accepted for poster presentation are:

  • Giovanni Bacci, Giorgio Bacci, Kim Guldstrand Larsen and Radu Mardare: On the Metric-based Approximate Minimization of Markov Chains
  • Simone Barlocco and Clemens Kupke: Automata Learning: A Modal Logic Perspective
  • Michael Bukatin and Jon Anthony: Dataflow Matrix Machines as a Model of Computations with Linear Streams
  • Kaizaburo Chubachi, Diptarama, Ryo Yoshinaka and Ayumi Shinohara: Query Learning of Regular Languages over Large Ordered Alphabets
  • Joshua Moerman: Learning Product Automata
  • Tianyu Li, Guillaume Rabusseau and Doina Precup: Neural Network Based Nonlinear Weighted Finite Automata
  • Alexis Linard, Rick Smetsers, Frits Vaandrager, Umar Waqas, Joost van Pinxten and Sicco Verwer: Learning Pairwise Disjoint Simple Languages from Positive Examples
  • Xiaoran Liu, Qin Lin, Sicco Verwer and Dmitri Jarnikov: Anomaly Detection in a Digital Video Broadcasting System Using Timed Automata
  • Guillaume Rabusseau and Joelle Pineau: Multitask Spectral Learning of Weighted Automata
  • Michal Soucha and Kirill Bogdanov: Efficient Active Learning with Extra States

The following top researchers will be invited speakers at LearnAut:
  • Kim G. Larsen (Aalborg University)
  • Mehryar Mohri (New York University & Google Research)
  • Alexandra Silva (University College London)

If you have not registered yet to the workshop, and if you are interested by its program, we strongly recommend you to do it as soon as possible (http://www.icetcs.ru.is/lics2017-registration.html). The early registration deadline is on May 5th.

Pressures on accommodation possibilities are high, the sooner you book one the better it is (a lot of hotels are unfortunately already full).

Looking forward to seeing you at Reykjavik!

Friday, April 14, 2017

Public service announcement for LICS (workshop) participants

This is a public service announcement. If you plan to attend a LICS 2017 workshop and/or the main conference, and you have not booked your flight and accommodation yet, I strongly suggest that you do so ASAP. Iceland is a very hot holiday destination these days and it becomes fully booked soon, especially during the summer months. We already have about 160 registered participants for the conference and accommodation is disappearing at a rate of knots.

Friday, April 07, 2017

Ten PhD positions in CS at the Gran Sasso Science Institute

The Gran Sasso Science Institute (GSSI - http://www.gssi.it/), a recently established international PhD school and a Centre for advanced studies in L'Aquila (ITALY), offers 10 PhD positions in Computer Science (CS).

The PhD program in CS is mainly concerned with heterogeneous distributed systems and their interactions. Different perspectives are offered to provide students with the necessary tools for the design, the implementation, the management and the use of distributed systems. The main research areas of interest are:
- Efficient algorithms for communication networks and social networks;
- Formal methods for systems correctness and analysis;
- Software engineering for efficient and resilient applications.

Apart from pursuing their own research studies, the successful candidates will have the opportunity to cooperate with members of the research group and of the Scientific Board, as well as with the frequent guests of the Institute. Detailed information about the CS research group and about the activities for the PhD program in CS can be found at http://cs.gssi.it/

The fellowships are awarded for three years and their yearly amount is € 16.159,91 gross. Moreover all PhD students:
- will have free accommodation at the GSSI facilities and luncheon vouchers;
- will have tuition fees waived;
- will be covered by insurance against accident and/or injury.

The application must be submitted through the online form available at http://www.gssi.it/phd/ and must be accompanied by the curriculum vitae of the applicant, and by a letter of motivation describing expertise and general research interests together with future plans and reasons for having chosen GSSI for PhD studies.

The deadline for application is: 31st May 2017 at 18.00 (Italian time).

Tuesday, April 04, 2017

18 postdoctoral positions at the Gran Sasso Science Institute

The Gran Sasso Science Institute offers 18 postdoctoral positions for research activity in Physics, Mathematics, Computer Science and Social Sciences.
Applicants must hold a PhD degree or an equivalent qualification. 

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

The application must be submitted through the online form available at www.gssi.it/postdoc/ by May 15, 2017 at 6 p.m. (Italian time zone).

For more information, please consult the Call for Applications at www.gssi.it/postdoc/ or write an email to info@gssi.it.

A description of research in computer science at GSSI is available here

Feel free to share this announcement as you see fit.

Saturday, April 01, 2017

The faculty is the university: The case of IMT Lucca

The physicist Isidor Isaac Rabi famously told President Eisenhower that "the faculty is the university." This is a quote I like to use when discussing with university administrators and I was reminded of it these days while reading opinions aired by several Italian academics on IMT Lucca, an Italian centre of advanced study and an international PhD school.

IMHO, a recent case of possible plagiarism involving an IMT graduate hasn't been handled well at all by the top management of that institution. However, to my mind, this event should not be used to debase the excellent work that our colleagues have done and are doing at that institute, which attracts to Italy and trains a good number of high-quality PhD students from abroad, and conducts cutting-edge research in its areas of interest. In fact, I do believe that schools of advanced study such as IMT can play an important role in the academic environment in Italy by attracting talent from abroad and nurturing Italian young researchers within an international research environment. IMHO, the variety those schools add to higher education in my native country is beneficial.

I would definitely encourage my (former) students to take up a PhD or a postdoctoral position within the SysMA group, to work with Rocco De Nicola, Mirco Tribastone and the young researchers in that group, five of whom are from outside Italy. I would also point people interested in control and dynamical systems to the DYSCO group, led by Alberto Bemporad.

These are just two examples from areas that are close to my own research interests. However, the quality of the faculty and of the postdocs and students at IMT is consistently high. I have had the pleasure of giving lectures on basic research skills to IMT students of a varied background, including students in cultural heritage, and thoroughly enjoyed interacting with them.

Summing up, my message to the colleagues who are currently forming an opinion on IMT Lucca based on the actions of its management is simple: "The faculty is the university." Look carefully at the (IMHO, excellent) work done by our colleagues working at that institute and form an opinion based on it, not on mediatic noise.

Wednesday, March 22, 2017

Accepted papers at LICS 2017

The list of accepted papers for LICS 2017 is now available at http://lics.rwth-aachen.de/lics17/accepted.html. Thanks to Joel Ouaknine and his PC for their work in selecting such a mouth-watering list of papers!

If you have not done so already, go ahead and register for the conference now. We strongly encourage prospective participants to register, and to make their travel and accommodation plans ASAP. Iceland gets literally fully booked early during the summer months.

Tuesday, March 21, 2017

Opinions on the ERC after ten years

I am collecting some opinions about the European Research Council (ERC) from researchers who have received funding from it, and from some who have not.

What is your overall opinion on the ERC? Do you think that it is good for European research?

My interest in this matter started because the ERC is ten (and so it might be a good time to draw a preliminary assessment of its impact on the European research environment) and was piqued by the opinions aired by the Italian physicist Sylos Labini who claimed that the ERC has become the main problem in European research funding. He says that there are three main problems with the ERC.
  1. The first is that it uses "research excellence" to mask political choices.
  2. The second is that rewarding today's excellence does nothing to support the excellence of tomorrow. Moreover, one does not reward excellent research by giving money to the top 5% of those who apply. 
  3. The third is that the ERC gives a bad example to national funding agencies in Europe, who also reward excellence. 
See also http://www.sciencemag.org/news/2017/03/10-europe-s-excellence-fund-faces-calls-change, where Sylos Labini makes a cameo appearance in this paragraph:

But some chafe at the singular focus on excellence. Countries in southern Europe have cut their research budgets during the economic crisis, and now ERC is further weakening these countries by essentially redistributing their EU contributions to the research powerhouses in the north, says Francesco Sylos Labini, a physicist at the Enrico Fermi Center in Rome. And it’s not just the money: “The few Italian researchers that get an ERC grant go to Germany or another country to do their research,” he says.

I do not a long piece of text. Just a few lines would do. I'd be grateful if you could contribute to this discussion by posting your comments.

You might also wish to read Helga Nowotny's short piece entitled ERC---the next ten years.

Monday, March 13, 2017

Rogers Hollingsworth on Major Discoveries of the American System of Science

Recently, I have been reading a fairly long study by historian Rogers Hollingsworth on what makes research organizations produce major discoveries. This talk he gave at the NSF summarizes some of the findings in that article. From around minute 50 in the presentation, the speaker presents some thoughtful closing comments on the current state of funding for basic science and on the effects that the involvement of politicians in making decisions on how to allocate that funding, and in monitoring and auditing the work of scientists, can have on science. For the little that it is worth, I found those thoughts worth mulling over.

Friday, March 10, 2017

Has the Feder-Vardi dichotomy conjecture been proved? (Take 2)

In this post, I mentioned that a paper by Arash Rafiey, Jeff Kinne and Tomás Feder claiming a solution to the Feder-Vardi  dichotomy conjecture appeared on the arXiv on the 11th of January. The result in that paper was also covered by Lance Fortnow in this blog post.

We now have another preprint, A dichotomy theorem for nonuniform CSPs (71 pages) by Andrei Bulatov, claiming a solution to this long-standing conjecture. (Thanks to Moshe Vardi for pointing this paper out to me.) Not surprisingly, Andrei's paper  uses "the algebraic approach that associates to every relational structure its (universal) algebra of polymorphisms."

I am not an expert on this topic, but I hope that those who are (and especially the prime movers behind the universal algebraic approach to the problem) will stop what they are doing, read this paper carefully and vet its correctness,

I reiterate what I wrote in my earlier post: "If the technical content of the paper is found to be correct by the community working on CSPs after careful peer review, this is a truly major result."

The Feder-Vardi  dichotomy conjecture seems ripe for a solution. We now have two papers, claiming a solution to that conjecture, that use very different techniques. I hope that they are both right and that the tools developed in those articles will find application in the solution of other problems.

Wednesday, March 01, 2017

Registration for LICS 2017 is now open

We are happy to inform you that registration for LICS 2017 and affiliated workshops is open. You can register for the conference and/or its seven co-located workshops by following this link.

As you will see, due to the pressure of the tourist industry (which has increased enormously since we made the bid for hosting the conference in 2015), we are forced to have Friday, 7 April, as early registration deadline. We strongly encourage prospective participants to make their accommodation and travel plans as early as possible, and the date for the early registration is meant to entice them to do so.

As you will see, the early registration fees for the conference are as follows:
  • Early registration fee (members of ACM, ACM SIGLOG, ASL, EATCS or IEEE): 64,000 ISK
  • Early student registration fee: 46,000 ISK
  • Early registration fee (others): 88,000 ISK
The regular registration fees include the cost of the rooms, technical equipment, four lunches (one per conference day), eight coffee breaks (two per conference day), welcome reception and conference dinner at Kolabrautin (three course meal with three glasses of wine per participant). The student registration fees include all the above items, apart from the conference dinner.

In order to meet ACM regulations, the registration fee for members is 25% cheaper than for non-members. We therefore strongly encourage prospective participants who are not members of the ACM, ASL, EATCS or IEEE to join one of those associations. When choosing which association to join, consider the following things:
  1. The EATCS annual membership fee is of 30€. (For students, that would give a two-year membership.) The EATCS sponsors the Kleene Award at LICS 2017 and its Bulletin of the EATCS is published in an open-access form.
  2. Information on ACM SIGLOG membership is available here. There is no need to have a separate ACM membership in order to join SIGLOG. 
  3. The ACM and the IEEE already take 36% of the registration fees and provide no financial sponsorship for the conference, apart from 100K ISK that were kindly offered to us by our friends in the Icelandic Section of the IEEE. 
  4. ACM professional membership costs 99 USD. 
  5. Membership of the IEEE Computer Society costs 60 USD.
  6. A discounted introductory rate for members of the ASL  is available to new regular members of the Association for the first two consecutive years of membership (US$47 in 2017 and 2018).
The LICS 2017 Organizing Committee hopes that this information helps and looks forward to welcoming you in Reykjavik for LICS 2017 and its seven affiliated workshops.

Sunday, February 26, 2017

Ten PhD positions at the Gran Sasso Science Institute

The Gran Sasso Science Institute (GSSI), founded in 2012 in L’Aquila (Italy) as Center for Advanced Studies of the National Institute for Nuclear Physics (INFN) and then established in March 2016 as a School of Advanced Studies providing post-graduate education, offers 40 PhD fellowships for the academic year 2017/18.
Amng others, the GSSI invites applications for 10 fellowships in  “Computer Science”, with emphasis on algorithmics, formal methods for concurrent systems, and software engineering. The official language for all PhD courses is English.

The fellowships are awarded for three years and their yearly amount is € 16,159.91 gross. All PhD students have free accommodation at the GSSI facilities and use of the canteen.

The application must be submitted through the online form available at www.gssi.it/phd/ by 31st May 2017 at 18.00 (Italian time zone).

For more information, please consult the Call for Applications at www.gssi.it/phd/ or write an email to info@gssi.it or call +39 0862 4280262.

Tuesday, February 21, 2017

Computer Science at Reykjavik University looks for a new dean

I hope that readers of this blog will consider  applying for this position and join the School of Computer Science at Reykjavik University. Come and help us shape the future of CS research and teaching in Iceland!

Reykjavik University seeks an ambitious leader to carry out the development of a growing School of Computer Science. The dean is responsible for administrative affairs as well as for leading the faculty's academic agenda. The dean reports to the Rector of Reykjavik University and is a member of the university's executive committee.

We seek candidates that have:
  • Strong strategic vision and the ability to shape and lead a team of faculty members and staff
  • Doctorate in computer science or related subjects
  • Academic teaching and research experience
  • Management, operations and leadership experience
  • Experience from industry or collaborations with industry
  • International experience

Reykjavik University's School of Computer Science provides education and research in computer science, software engineering and related subjects. The School offers BSc, MSc and PhD degrees. External accreditation committee for doctorate studies assessed the school to be the strongest in Iceland in its field and one conducting top-level international research (http://www.ru.is/media/td/SCS_accreditation.pdf). The school has around 850 enrolled students and nearly 30 faculty and staff members.

For further information, please contact Ari Kristinn Jónsson, Rector (ari@ru.is) and Sigríður Elín Guðlaugsdóttir, Executive Director of Human Resources (sigridureg@ru.is) tel: +354-599-6200.
Applications should be submitted before March 15th, 2017, through our applications website: radningar.hr.is.

The role of Reykjavik University is to create and disseminate knowledge to enhance the competitiveness and quality of life for individuals and society, guided by good ethics, sustainability and responsibility.

There are four schools within the university; School of Business, School of Computer Science, School of Law and School of Science and Engineering. Education and research at RU are based on strong ties with industry and society. We emphasize interdisciplinary collaboration, international relations and entrepreneurship. Reykjavik University currently has around 3600 students and 240 employees.

Friday, February 10, 2017

An Interview with Thomas Henzinger, President of IST Austria

The Institute of Science and Technology Austria (ISTAustria) is a young international institute dedicated to basic research and graduate education in the natural and mathematical sciences, located in Klosterneuburg on the outskirts of Vienna. Our colleague Thomas Henzinger has been the president of the institute since its birth, and I thought that it might be interesting for the readers of the Bulletin of the EATCS and of this blog to hear about the development of IST Austria and his opinions on how to create an excellent research institution.

I interviewed Thomas Henzinger (abbreviated to TH in what follows) via email and present his answers to my questions in what follows. 

LA: Could you briefly introduce IST Austria, its aims and its current state of development? 

TH: The Institute of Science and Technology (IST) Austria was founded in 2006 with the goal to build in Austria a world-class institution for basic research and graduate education in science. Currently we are half-way towards our goal of 90 research groups in biology, physics, chemistry, mathematics, and computer science.

LA: As far as I know, IST Austria only started its operations in 2009. It already underwent a successful,  international evaluation in 2011 and has grown remarkably since then. In your opinion, which strategic decisions have been crucial in making IST Austria a high-quality research institute in such a short period of time and in attracting top-class scientists at various stages of their careers to it?

TH: The most important decision of the Austrian government was to start IST Austria from scratch, independent of any existing institution, and to give the Institute maximal freedom in designing itself.  Whenever we take a design decision at IST Austria, we consider primarily one criterion: how can we best compete for the most promising young faculty and the most talented PhD students in the world?  Three of our most important design decisions, all guided by this criterion, were: (1) We hire all young faculty on a tenure track, giving them both independence and the opportunity to be promoted to a full professorship, based solely on performance. (2) We never assign open faculty slots to research topics or scientific disciplines, but always try to offer our positions to the most promising candidates we see, independent of their field. (3) All PhD students are admitted centrally and must complete a multidisciplinary curriculum and rotation projects with several professors before they embark on their thesis research.

LA: So far, which aspects of the development of IST Austria are you most proud of?  How would you like to see IST Austria grow in the near future? Do you think that the institute  will expand its research in computer science and, if so, how?

TH:  I am proudest of the fact that 30 of our 45 professors are funded by the European Research Council.  I believe that relative to our size, this makes us the most successful institution in Europe. Among our 45 current professors, there are 8 computer scientists. We hope to double both numbers over the next  10 years.

LA: I recently watched the video of the panel discussion "IST Austria: On the Way to the Top: What Makes a Research Institution Excellent?'', which you chaired, on YouTube. It was truly inspirational. However, since you were running short of time, you did not get a chance to express your views on the topic and I, for one, would be very interested in hearing them. So, in your opinion, what makes a research institution excellent? Would the advice you would give to a computer science department in a European university that strives for excellence be any different?

TH:  Most science administrators agree that the key to excellence is the principle "hire the best scientists and leave them alone." It is easy to advocate this principle, but it is difficult to implement it. The temptation to think strategically top-down -to focus on research areas when hiring professors, on research projects when hiring students, on industrial and societal needs when asking for more funds- is very hard to resist.  But giving in to that temptation usually means leaving the quickest path to scientific excellence.

LA: To your mind, what is the role of PhD education in achieving research excellence? Would you have any advice to share with us on how to run an international PhD granting institution in Europe that is capable of attracting very strong students? 

TH: Attracting top PhD students from all over the world is critical because top students attract top professors. In fact, in my experience it is more difficult to attract top students: they are often more "brand driven" than professors, and it takes a long time for an institution to build up a world-wide reputation that trickles down to undergraduates looking for PhD programs. I wish I had a quick solution for this problem.

LA: You have been the President of IST Austria from its inception. This must be more than a full-time job. However, at the same time, you have managed to remain very active in research, pursuing new avenues and maintaining a research group. How did you do so? Is there any "secret" you'd like to share with us?

TH:  It is difficult to "context switch" between administrative and scientific problems. But the opportunity to talk with my students and postdocs almost on a daily basis is what keeps me sane. It is important also because it allows me to see the Institute and its administration from the "other" side, and because it  gives me greater credibility when trying to recruit faculty.


Tuesday, January 31, 2017

Call for expressions of interest for permanent positions at the Gran Sasso Science Institute

I have been asked to distribute this call. The Gran Sasso Science Institute is a new, ambitious international centre for advanced studies and PhD school. Give this opportunity a thought. 

Gran Sasso Science Institute - Computer Science Area

Expression of Interest for Faculty Positions

Gran Sasso Science Institute (GSSI) is a new Center for Advanced studies and PhD School established in L’Aquila (Italy).
The Computer Science Area of GSSI (http://cs.gssi.infn.it/phd-program/information/) invites expressions of interest for permanent positions at the level of Full or Associate Professor, and for tenure track (Ricercatore TD – B), and temporary (Ricercatore TD – A) research assistants. Highly qualified candidates with a strong research background in the following fields: cryptography, network security, algorithms, and software engineering are encouraged to apply. The Institute is particularly interested in (potential) leaders of multi-disciplinary research groups in the above fields.
Candidates must have an excellent record of publications, a clear potential to promote and lead research activities, and a specific interest in teaching at the postgraduate level to skilled students recruited internationally.

Applicants should submit their expression of interest by sending
  • a motivation letter in which also the position(s) of interest are specified.
  • a curriculum vitae
  • a list of publications,
  • a brief research statement.
Applications (and questions regarding the application process) must be submitted in electronic form, preferably by April 1st 2017, to eoi-cs@gssi.it.

Please note that this is not a permanent job vacancy advertisement. The expressions of interest received will contribute to the decision of the Gran Sasso Science Institute whether or not to open official calls, their number and the selection procedures.


1- Duties
Teaching post-graduate courses, leading internal seminar and tutoring PhD students. All activities are in English.
2- Salary
The salary will be determined on a personal basis, also taking into account past positions covered abroad. Indicative figures of the gross amount for starting (minimum) salary are:
  • Professor (prima fascia) € 72.431
  • Associate Professor (seconda fascia) € 50.831
  • Assistant Professor, tenure track (ricercatori TD – B) € 34.898
  • Assistant Professor, no tenure track (ricercatori TD – A) € 34.898
Net income may vary depending on income taxes, local taxes, retirement plan, health care deduction and tax exemptions. Professors who have held a tenured position outside Italy for more than three years (at the corresponding level) might be eligible for a partial recognition of past services, depending on specific legal constraints.