8
$\begingroup$

I am currently facing a situation that I am not sure how to handle.

Basically, there is this problem $A$. Problem $A$ has been a hot topic in the past $5$ years. Last year, a paper was published in a very reputable journal (IEEE Transactions on Information Theory) that proposed a new algorithm that consists of $2$ sub-algorithms, $A_1, A_2$ that are both used to solve the problem. Here is the caveat, Algorithm $A_1$ was shown to eventually converge without any run time gurantee (shown to converge with finite number of steps), while $A_2$ was shown to take $O(n^5)$.

My paper is essentially replacing $A_1$ with a new algorithm which is guaranteed to terminate correctly in $O(n\log n)$, hence bringing the overall time complexity when combined with $A_2$ to $O(n^6\log n)$.

So far, so good. I am fairly certain the paper can get accepted into the same journal since the new algorithm is highly non trivial and provides lots of new insight on the problem. However, 2 weeks ago, I was wrapping up everything and decided to give algorithm $A_2$ another read as well as its proofs. That's when I faced some problems.

One of the proofs in that paper is faulty, beyond repair. The author did a very big jump, and I managed to come up with a counter example essentially showing that the theorem he "proved" is false. I tried to fix his algorithm, but I couldn't. So I tried approaching it from a new perspective using his method, and I managed to get a new algorithm that replaces the faulty $A_2$, but it ran in $O(n^6)$.

Here is my problem, my advisor thinks I should definitely include this in my paper as I've essentially replaced both algorithms $A_1, A_2$. However, If I just say I have an $O(n^6)$ when there is an $O(n^5)$ known, its going to raise eye brows. The only way I can pass this is if I actually take jabs at $A_2$ and show that its actually wrong, but I feel that "attacking" a paper in my first publication is a really bad idea.

Any ideas?

EDIT: Contacted the author and he acknowledged the mistake. He agreed to be mentioned in the new paper and he showed quite the interest in the $O(n\log n)$ algorithm. He also contacted IEEE Transactions to see if they can add a correcting note. This went way smoother than I thought it would. Thanks everyone!

Improve this question
$\endgroup$
6
  • 9
    $\begingroup$ Finding and fixing a flaw in a paper is not a bad thing and a good scholar would not consider it an "attack", but rather the normal process of research $\endgroup$ – Max New Sep 21 '18 at 18:40
  • 7
    $\begingroup$ It's not bad at all, people do it all the time and nobody gets offended if you point out that the algorithm is wrong (if it indeed is). $\endgroup$ – domotorp Sep 21 '18 at 18:40
  • 7
    $\begingroup$ Seconding the two comments above; with a small caveat. Phrasing is important. Saying "However, there appears to be a flaw in a key lemma, and the stated runtime guarantee does not follow from the analysis; it is unclear if it holds." is reasonable; saying "The authors' proof is wrong and beyond repair, and their algorithm does not work." may be less of a good idea. $\endgroup$ – Clement C. Sep 21 '18 at 21:36
  • 6
    $\begingroup$ You should also consider contacting the author privately before submitting the paper and/or making it public. Although it sounds like you and your advisor are confident that there is really a counterexample to one of the author's claims and that the original algorithm is flawed, there is a small chance that you are misunderstanding the argument and/or that there is a simple workaround you are overlooking. Being in clear communication with the original author will make your life easier. $\endgroup$ – Noam Zeilberger Sep 22 '18 at 11:42
  • 4
    $\begingroup$ @user3508551: Here's a secret -- getting a polite note from a graduate student saying that your theorem is broken actually feels, on net, good. Yes, of course you feel sad to learn you made a mistake and your theorem is wrong, but on the other hand, getting concrete evidence that someone smart spent a lot of time reading and thinking about your work is very rewarding. $\endgroup$ – Neel Krishnaswami Sep 24 '18 at 9:07
12
$\begingroup$

I think the same standards apply, regardless of whether it's your 1st or 100th publication. If you think you've found a mistake in a published paper, a common courtesy is to first contact the paper's authors for a clarification, as Noam suggested in the comments. If the authors confirm that it's indeed a mistake, you can indicate that in the paper (cite it as "private communication"); this should make the review process smoother.

When pointing out people's mistakes in print, gentle understatement is a good practice. "There appears to be a mistake in the proof" should be gentle enough. Having a counterexample certainly helps.

Improve this answer
$\endgroup$
2
  • 5
    $\begingroup$ Contacted the author and he acknowledged the mistake. He agreed to be mentioned in the new paper and he showed quite the interest in the $O(n\log n)$ algorithm. He also contacted IEEE Transactions to see if they can add a correcting note. This went way smoother than I thought it would. Thanks you! $\endgroup$ – user3508551 Sep 23 '18 at 17:17
  • 1
    $\begingroup$ That's great news! Hopefully the paper will be accepted soon -- when it is, maybe you'll post a link here so we can read it :) $\endgroup$ – Aryeh Sep 24 '18 at 18:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.