# 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 Sep 21, 2018 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). Sep 21, 2018 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. Sep 21, 2018 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. Sep 22, 2018 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. Sep 24, 2018 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! Sep 23, 2018 at 17:17