I am a student in computer science and I recently started working on my M.Sc. thesis. Now I am reading a 2011 paper with about 170 citations that was published in a well-known conference.

In part of the paper, the author briefly states the complexity of their algorithm (in just one line) and claims a complexity order that I believe is false. But I am really in doubt because I think if there was a problem with that paper, that should have been caught earlier by the editorial board.

I want to know, actually how common is it for such errors to be found in papers published in a well-known conferences?

  • 4
    The general question is hard to answer. The specific question is answerable, but might be better on the computer science stack exchange.
    – Compass
    Commented Jul 2, 2015 at 16:22
  • 9
    Which error? Have you proved the author's claim wrong? For the moment, you just think it wrong: prove your idea, first, and then claim that the paper is wrong. Commented Jul 2, 2015 at 16:23
  • 1
    @MassimoOrtolano they wrote their algorithm and mentioned that its complexity is X. I went through the algorithm and found that Its complexity should be Y (but even with a formal proof there is the risk of a mistake). anyway as that is a (another) technical problem, in this question let focus on a more general problem to find answers or similar experiences.
    – user35129
    Commented Jul 2, 2015 at 17:19
  • 1
    You (probably) found such a problem in just one paper. How can you claim it is "common" to find errors?
    – nplatis
    Commented Jul 2, 2015 at 17:59
  • 8
    @nplatis I never had such claim. I just asked about how much is it common to estimate a "prior probability" for my issue.maybe the problem is with my title(I will change the question title to clarify).
    – user35129
    Commented Jul 2, 2015 at 18:57

4 Answers 4


I'll try to give a general answer from a non-CS perspective.

tl; dr: yes, there are errors out there. A lot of errors, clerical and not, even in oft-cited papers and books, from any field. It's inevitable: though they do their best to avoid errors, authors are human after all, and reviewers are humans too (I know, you never find a damn robot when you need one). Thus, whenever you read a paper, maintain critical thinking.


I'll start the too long section with an anecdote. When I was working at my master's thesis, some twenty years ago, I needed a result published in a much cited paper from a renowned author in the field of electromagnetics. At the time, (almost) young and inexperienced, I thought that papers were always absolutely right, especially when written by recognized authorities. To practice the technique of the paper, I decided to rederive the results: after a week spent redoing the calculations over and over again, I couldn't find the same final equation. I was able to discover the correct equation – the one I was finding – in a book published later by the same author. Indeed, it was a clerical error that absolutely didn't change anything in the paper, but it was annoying and taught me an important lesson: papers and books contain errors. And, of course, I later published papers with mistakes in equations (not for revenge!) [*].

After that first experience, I've discovered that you can find more fundamental errors, even in well known books and papers. I'll give you here a few examples, taken from different fields, to underline how broad the phenomenon is (in bold, the mistaken claim; within parentheses, the field):

  1. (Classical mechanics) In Newtonian mechanics, the correct equation of motion in case of variable mass is F = dp/dt. This statement can be found in many classical books about newtonian mechanics, but it is plainly wrong, because that equation, when the mass is variable, is not invariant under Galilean transformations as it is expected in Newtonian mechanics (actually, the concept of variable mass in Newtonian mechanics can be misleading if not properly handled). For a deeper discussion see, e.g., Plastino (1990), Pinheiro (2004) and Spivak's book Physics for Mathematicians, Mechanics I. As a curiosity, that wrong equation is used by L. O. Chua in this speech (14:50 min) as an example to introduce the memristor.
  2. (Circuit analysis) Superposition can't be applied directly to controlled sources. It was just a few years ago when I came across this statement for the first time, and I was stunned: hey, I've applied superposition to controlled sources since I was in high school, and I've always get the right result. How it possibly can't be used? In fact, it can be applied, the important thing is to apply it correctly, but there are really many professors (I have several examples from Italy and US) who don't understand this point and fail to notice that the proofs of several theorems in circuit analysis are actually based on the applicability of superposition to controlled sources. For more on this, see e.g. Damper (2010), Marshall Leach (2009) and Rathore et al. (2012).
  3. (Thermodynamics) The Seebeck effect is a consequence of the contact potential. This false statement can be frequently read in technical books and application notes about thermocouples.

À propos of my own errors, a couple of weeks after having written this answer I discovered an error in an equation of a published conference paper which I co-authored. A fraction that should have been something like -A/B became B/A. Hey – I told one of the other authors – how could we possibly have written this? And how did it get past the reviewers? The fact is, that that equation was associated to a simple, well-known, example given in the introduction, an example so simple that probably neither us authors nor the reviewers gave a second look at the equation (of course, how can anyone write this wrongly?). I feel that many clerical errors like this one happen because of last-minute changes to notation: you have almost finished the paper and you realize that you could have employed a better notation... so, let's change it on the fly! And here is where certain errors sneak-in. Avoid last-minute changes, if you can.

  • 18
    Absolutely concur. Heck, I know somebody who recently found an error in Einstein's math, in which Einstein used the incorrect domain for some functions in general relativity. It doesn't affect any of the results, because for every case that mattered the incorrect domain happened to be identical to the correct domain, but nonetheless the error was there and none of the vast number of physicists who'd tangled with those equations had ever noticed before...
    – jakebeal
    Commented Jul 2, 2015 at 21:15
  • 6
    I once had to review a paper. They claimed a result which I knew from a (privately, not yet published) communicated effort to have a counterexample. I had to go through the proof line-by-line, and found the error in the statement "Obviously, it holds". To any sentence starting with "Obviously", I'd like to add "Yeah; right". Commented Jan 18, 2016 at 17:03
  • 2
    Fearsome are "as one easily sees", "trivial", "obviously", but most fearsome of them all is "it can be shown" Commented Jan 18, 2016 at 18:44
  • 2
    Needs a +2 just for the dependent sources part. I now normally says that "you can do it, but it's better avoided" (cause normally doing it correctly will null the advantages of using superposition, that is. And most people will simply open the source in example 5 of your Rathore reference, and wreak havoc. ). Very nice answer.
    – Rmano
    Commented Aug 21, 2018 at 17:28
  • 1
    @Rmano Thank you very much! Since you seem to be Italian, we had several years ago a discussion about this topic in an Italian forum. The discussion, which started as a poll, can be found here and I write under the nickname DirtyDeeds: see the messages [12] and [13] in particular. If you want to discuss this or similar topics I'd happy, just ping me in the Ivory Tower chat: I might not have much time at present but I'm hoping for better times. Commented Aug 21, 2018 at 20:19

TL;DR: The number is probably a double digit percentage.

I made a outlier detection algorithm for neuroscience data extracted from neuroscience journal articles. It is detailed in "Modeling of activation data in the BrainMap(TM): Detection of outliers" http://onlinelibrary.wiley.com/doi/10.1002/hbm.10012/abstract The redundancy in coordinates and text allow me to catch 'strange' data, some of which are typos in the original article. I have not made a statistics on the number of articles with errors but perhaps 1% or more have the issue. Note here that the typos are rather minor (e.g., a sign error in a single coordinate among many other reported numbers). It does not affect the overall conclusion. (For the interested: Results for my database available here: http://neuro.compute.dtu.dk/services/brededatabase/index_lobaranatomy_novelty.html)

Within the medical domain John Ioannidis has made a number of studies for estimating errors in claims in articles. The famous "Why Most Published Research Findings Are False" http://journals.plos.org/plosmedicine/article?id=10.1371/journal.pmed.0020124 gives a theoretical estimate where the assumptions are probably not entirely correct, but following his argument there might be a double digit number of percentage "false". In "Contradicted and initially stronger effects in highly cited clinical research" https://jama.jamanetwork.com/article.aspx?articleid=201218 he found that in 16%-32% of the cases with highly cited original clinical research studies their claims were contradicted by subsequent studies.

Peter C. Gøtzsche in "Data Extraction Errors in Meta-analyses That Use Standardized Mean Differences" found discrepancies in 37% of meta-analyses. Ironically there was a comment for the Gøtzsche-paper pointing out a discrepancy in that paper.

These examples are perhaps not so relevant for computer science. I do think that typos occur now and then. I recently found what I believe were typos in equations in applied computer science articles. The typos does probably not affect the results. I would say - generally - that errors in computer science articles are not necessarily rare.

Update 28 August 2015:

There has just been published a description of a large series of replications of psychology experiments, see http://www.sciencemag.org/content/349/6251/aac4716.abstract

Among its reported results are: "Ninety-seven percent of original studies had significant results (P < .05). Thirty-six percent of replications had significant results".

  • (-1) Unfortunately, finding "false" claims is much more complicated than this. The fact that "Ninety-seven percent of original studies had significant results (P < .05). Thirty-six percent of replications had significant results" is not strong evidence (in any way) that roughly 2/3 of the original claims were flawed.
    – Cliff AB
    Commented Mar 16, 2019 at 23:35
  • I am not entirely sure what you, @CliffAB, allude to wrt. the Open Science Collaboration study. They claim "high- powered designs": "median power was 95%". While they (and I) acknowledge "There is no single standard for eval- uating replication success" the various methods, p-value significance, effect size-effect size plot and "subjective" replication, make a good case for that the majority of the original studies over-estimate the effect size to a considerable degree. Commented Mar 17, 2019 at 14:36
  • If the claim "median power [should be] 95%" was made somewhere, then I see your point (although again, it's more complicated than that). I can't find that in the link, is it in the full text? But in general, the results shown in the link is very consistent with the "p-value filter" of publication; we should expect the results that lead to publication have an upward bias. But that's much different than being wrong.
    – Cliff AB
    Commented Mar 17, 2019 at 16:03
  • The power analysis is described in the supplementary material science.sciencemag.org/content/sci/suppl/2015/08/26/… page 3-4, last paragraph page 3, first paragraph page 4. That PDF is also linked from science.sciencemag.org/content/suppl/2015/08/26/… Commented Mar 18, 2019 at 14:40
  • Thanks for the explanation. My (-1) turned to a (+1).
    – Cliff AB
    Commented Mar 18, 2019 at 14:42

Massimo Ortolano gave many non-CS examples, so I give a CS one: in the paper of Alan Turing that gave birth to Computer Science, there were many errors in the proof.

However, in my opinion, although there are many errors in papers, these errors are only in the small details. For papers published in well-known conference, their main idea are very unlikely to be wrong.

As you mentioned that the statement about complexity is only one line, obviously without proof, this is not the main focus of the paper. I will not be surprised if there is error in such a small detail.

If I were you I would try to prove what you are thinking, this will help you to understand the paper deeply. And if it is actually wrong, you can notify the authors or publish your proof if the error is important enough.

  • 1
    I guess you mean: most errors are in minor details for papers in good volumes. Certainly crucial errors do happen, even in top journals.
    – Kimball
    Commented Jul 3, 2015 at 12:48
  • @Kimball: yes, that's what I mean. My English is not so great.
    – sean
    Commented Jul 3, 2015 at 13:20

As part of my graduate study we had to analyse several somewhat well-known papers in very reputable journals, published some 5 to 10 years before with no negative comments (yes, it was the time before Internet made such searches trivial). We found a glaring error in the central theorem of one of them. Not just the proof, the result was wrong. Sorry, I don't remember details (it's been some 25 years).

Yes, the plural of anecdote isn't data. But a data point to be considered.

To your question: If you are in doubt, check it carefully. Ask others to help you out if you get stuck. Yes, checking if previous work is right is part of research, as is trying to extend or simplify it.

You must log in to answer this question.