# Is it a bad idea to critique someone's paper in my first publication?

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!

• 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 – Max New Sep 21 '18 at 18:40
• 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). – domotorp Sep 21 '18 at 18:40
• 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. – Clement C. Sep 21 '18 at 21:36
• 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. – Noam Zeilberger Sep 22 '18 at 11:42
• @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. – Neel Krishnaswami Sep 24 '18 at 9:07

• 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! – user3508551 Sep 23 '18 at 17:17