Wednesday, December 13, 2017

Tenure-track positions in CS at Reykjavik University

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

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

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

Tuesday, December 05, 2017

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

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

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

Dear Mr Foer,

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

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

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

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

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

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

Looking forward to your reaction, with best regards,

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

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

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

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.