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