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 by September 18, 2017 at 18.00 (Italian time zone).

For more information, please consult the Call for Applications at or write an email to 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.

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

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

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!!!!!