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:
Post a Comment