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.





No comments: