Note (8/19/17): The authors have retracted their claim following the discovery of a counterexample by Ross Willard. However, there has been other progress on the dichotomy conjecture as explained in Process Algebra Diary.
Original Post:
Arash Rafiey, Jeff Kinne and Tomás Feder settle the Feder-Vardi dichotomy conjecture in their paper Dichotomy for Digraph Homomorphism Problems. Jeff Kinne is my academic grandchild--how quickly they grow up.
Keep in mind the usual caveat that this work has not yet been fully refereed and vetted by the community, though there is no reason to think it won't be (though some skepticism in the comments).
A homomorphism from a graph G = (V,E) to H=(V',E') is a function f:V→V' such that if (u,v) is in E then (f(u),f(v)) is in E'. For a fixed graph H, define L(H) as the set of graphs G such that there is a homomorphism from G to H.
If H is just a single edge then L(H) is the set of bipartite graphs. If H is a triangle then L(H) is the set of 3-colorable graphs. If H has a self-loop then L(H) is the set of all graphs.
L(H) is always in NP by guessing the homomorphism. In 1990 Pavol Hell and Jaroslav Nešetřil showed the following dichotomy result: If H is bipartite or has a self-loop then L(H) is computable in polynomial-time, otherwise L(H) is NP-complete. There are no undirected graphs H such that L(H) is not in P or NP-complete.
In 1998 Tomás Feder and Moshe Vardi conjectured that even for all directed graphs H, L(H) is either in P or NP-complete. Rafiey, Kinney and Feder settle the conjecture by showing a polynomial-time algorithm for a certain class of digraphs H.
Details in the paper.
Sorry to be so cowardly as to post anonymously but...
ReplyDeleteOn one hand, if this is correct, it's outstanding. As good as Babai's result, to me.
On the other hand, I asked four experts about this paper when it appeared on arXiv a few weeks ago. Their responses ranged from: 1) "Maybe." 2) "It would be amazing if this were true, but I'm pretty doubtful." 3) "This is not the first version of the paper I've seen, and the previous version was abandoned by expert reviewers as too unclear." 4) "I know a counterexample to their approach."
So yeah, I think it needs a pretty thorough review before we get too excited. (But as I said, if it holds up it would be truly phenomenal.)
I'm wondering why they are pretty doubtful? Is it because the authors are not "superstars"? or is there a better reason?
DeleteI think they are doubtful because of several troubling factors. Big results like this need big and thorough processes to solve them, full of reflections and serious discussion, and more importantly full transparency.
DeleteLet's look at Babai's great result: a very long paper appears in ArXiV, by someone who actually worked decades on this and related problems. The paper is full of details, with a clear explanation of the new ideas enabling the breakthrough, with a transparent process of vetting and proof-checking, and clear caveats from Babai's about the paper not being peer-reviewed, and a world-wide tour by the author of the highest-quality of technical seminars.
And even then, an alleged big gap was found in the proof! (Only to be fixed later).
Is this what is going here? I don't know. Maybe it is. But as Luca Aceto mentioned in his blog post, the author order has changed throughout the process, and it isn't clear what is the new idea that enabled this big result.
Actually, this is a good opportunity for the authors to clarify the doubts raised, talk to the community, explain things in a transparent way. I'm sure some of the authors do read this blog from time to time.
Perhaps Lance can ask his academic grandchild to clarify this.
The authors put a video online, to explain their new ideas. Why not read it?
DeleteI don't understand why the order of the author is relevant in any way, and why you write it in the same sentence with the new ideas.
What do you mean when saying "it is a good opportunity to clarify the doubts"? Should they write that they worked hard on this problem? I'm not sure it is possible to explain their ideas as a response to a post.
I suppose they will submit the paper to a conference / journal, and the reviewers should actually read it, and see what are the new ideas.
So your main argument is that since Babai's proof took so much time to verify even if he writes as clearly as possible, then so must be for these 3 *unknown* guys. Not fair.
DeleteSpeaking of transparency: On the other hand if some people, as you claim, have specific doubts, they should make these doubts public (where can I find these claimed doubts? Do they appear somewhere? Have they been communicated to the authors?) Also, if a person has counter examples to their approaches, these should be made public as soon as possible. I do not see why these are kept in private.
I also do not understand the sentence "it isn't clear what is the new idea that enabled this big result". Did you watch the videos? Did you read the very high level idea presented in the paper? I am far from an expert, but after reading their paper (quite a few times) I see their point. Still, I cannot judge if the techniques are new/excited etc. but what does it matter? It's not the first time that an awesome result has been proved by using old tricks...(TSP through matching by Ola Svensson pops into my mind)
I believe your comment is not in good faith and not fair for the authors.
But I quite strongly agree, let's wait what the experts/reviewers are gonna say and what would be the reaction to potential problems by the authors, but not jump (yet) to any unjustified conclusions.
GS
You probably mean Moemke-Svensson. Good to cite results correctly.
DeleteTo clarify: the first and third anonymous comments are from different people. I am the anon from the third comment. So for your suggestion that the counter example be shown to the authors, I agree. If I had such an example I would have sent it to the authors immediately.
DeleteAnd if they do not reply to this promptly I would then be skeptical of the veracity of the proof.
My bad. I got confused with the other single author TSP paper. My apologies.
DeleteGS.
WELCOME to Theory Track A -- where we assess not just novelty, but also correctness based on who the authors are (not), under the auspices of anonymous "reviewing".
DeleteOh and by the way, we don't do journals here; too slow for the swiftness with which our field progresses.
On the contrary.
DeleteAs explained above, it doesn't matter who the authors are. What matters is that big results such as these require extreme scrutiny and cautiousness before claiming to have been settled. Even in the case of known mainstream researchers like Babai, the proof had to be checked and even non-trivially corrected before claiming victory.
So let us wait before claiming the conjecture has been settled.
And we do have journals, and major results should and are submitted to journals.
Also, the Dichotomy Conjecture is not in Theory Track A. More like Track B, though I would say in between.
Moreover, if the authors do not want people to assess publicly the correctness of the proof, they would have done better to submit it directly to a journal without posting it online.
Finally, I wish the authors good luck and send my greetings if indeed the proof is correct. This will be a truly great result.
@NotOriginalAnonymous.
DeleteI agree, let's wait and avoid any premature comment (like "i doubt" etc) Given the authors' expertise in homomorphisms (as far as I could judge) It wouldn't surprise me to be actually correct, or at least in the correct path.
you talk (on your first comment) "this is a good opportunity for the authors to clarify the doubts raised"
Are there any particular doubts raised?
-If yes, then I (we all) expect a shift answer from the authors, otherwise naturally they loose credibility.
-If yes, what are the doubts? Given the importance of the result, I think it would make sense if we were all aware otherwise such vague claims put people down from actually trying to read the paper (if some experts raised serious and concrete doubts, I would wait before they are settled and then read it)
-If no, how this claim is justified?
What I find something worth noting is that the videos are from Summer but the paper was posted in January. I assume there was a lot of (internal? external?) debate during this period. Probably some issues where raised and the authors felt they dealt with them in a satisfactory way, thus the online posting. If not, they I invite the people had (and obviously still have) the original doubts to enlighten us all.
As I said I am far from expert in Homomorphism stuff etc. but the idea (as far as I understood it) makes sense to me. Of course we must make sure that all details are correct (man, it's a heavy paper)
Also, since the result is basically algorithmic, I think it fits maybe better in track A. But that's irrelevant, either it's correct or not :)
Bests,
GS
Lance, what has changed since I posted this on my blog? Has anyone examined the proof in some detail? You seem to think so, at least judging from your post.
ReplyDeleteThis is a very important result and it is certainly worth the time of the experts to go through the proof in detail, so that a consensus is reached.
@notOriginalAnon:
ReplyDeleteWhat a disingenuous response. I was commenting on a broader issue, of which sentiments like "I doubt" as in above is a telltale symptom.
A paper such as Babai's would not be accepted to STOC as readily as it was the case for Babai's (which we now know was hasty) if it came from lesser known authors. Journals do not carry as much weight as they should in key places such as faculty hiring.
You sound like a typical beneficiary of the system I am criticizing and will likely pretend to miss and nitpick at the points I am making while adding nothing new. I am signing off.
You're barking up the wrong tree here. Out of all the vast amount of problems I'm sure the TCS community has, just like any other community of humans, discrediting people for CORRECT proofs is not one of those. What stands out in TCS, like mathematics (as opposed to social sciences, or even physics) is that it has a completely objective criteria for evaluating the correctness of results.
DeleteIf the proof of the current paper is found correct the authors will get the full credit they deserve (and in which order they choose to). But until then there is nothing wrong in casting healthy doubt about the correctness of the proof. Because, the truth in our field is revealed quickly: either the proof is correct and complete, or not. It's actually an easy exercise to check proofs in our field, unless they use extremely deep concepts, which this paper doesn't seem to.
On a broader issue, you and other commenters above seem to claim there's a problem in TCS A with discrediting or doubting correct proofs. Can anyone name those papers of major results that were thought to be wrong but were later found out to be correct? I can't recall even one instance, but maybe they do exist. (Note that I claim that even in such cases not much harm has been done).
Dear NotOriginalAnonymous,
DeleteAs you very well know, there is nothing wrong in doubting. The problem is when somebody doubts without any real evidence just for the sake of it. And this is where are disagreement arises. Doubting publicly without real evidence (unless I'm missing something major here) is not what I would call "healthy".
Do I also doubt? Yes I do! But in the sense I wouldn't bet my savings account that it's a correct (or delta close to) result. But I will not go into the negative psychology path and start casting vague public doubts, especially when I think it has some fair chances of actually being correct! It's not fair to the authors and it does not add anything constructive at the moment.
Again, you have the right to think anyway you like. It's just a disagreement on how to approach this, and similar, situations.
Until and unless concrete evidence of doubt are given (I am still waiting the 1st anonymous to clarify the claim that counterexamples are known, if they were communicated to the authors, and how they reacted), let's not advance in "doubts" but let's wait in a positive and constructive way.
GS
Is it good to publicly state an issue if there is one? I am not sure. In Babai's case it was communicated directly to him and he was given the ability to announce it himself and also a fair chance to fix it. Seems like the polite way of handling the situation to me. Of course if a fair amount of time has passed since any issues have been communicated to the authors and they have not fixed it or publicly announced that they are aware of problems then it is fair to publicize the issues.
Delete@Yet another anonymous
DeleteI think it depends on many factors which I will not go into detail here. But if there are public doubts and public statements of "counterexamples" I think it is fair to actually ask about them otherwise it keeps people from trying to read it.
I think it's irresponsible to announce publicly about some vague potential issues on the paper: either don't say anything (maybe the polite thing to do until the issue is fixed one way or another), or say the whole story so that readers have the whole info otherwise any reader might very well be prejudiced.