4

I've read a certain 'extended abstract', published in conference proceedings, that presents a useful mathematical analysis of a computational problem and uses that to provide a sketch for an algorithm to solve the problem. The sketch lists the general (well-known) techniques on which the algorithm is based, but doesn't explain the algorithm in detail and is in particular not detailed enough to see that the claimed complexity of the running time holds.

The extended abstract is quite old and there's no trace of a publication that completely describes the algorithm from the extended abstract.

I have attempted to 'reconstruct' the algorithm from the sketch, but I've been unable to achieve the claimed bound on the running time and I believe the author has been mistaken in his bound (and that therefore the sketched algorithm is rubbish). When I mentioned this to my advisor, he replied that since there is no 'follow-up' of the extended abstract, the algorithm is probably rubbish. (the author is still alive and in academia, so absence can't be the reason not to publish)

The mathematical analysis was actually quite useful to create another (significantly different) algorithm for the same problem, which unfortunately has a worse behaviour than the claimed bound from the extended abstract.

I might be able to publish something related to the problem, but I'm not certain my results will be good enough. Additionally, I might be able to prove a lower bound strictly higher than the upper bound claimed in the extended abstract, thereby contradicting* it.

So, concretely, I'd like to know the following:

  1. Is there a place where the author could have published a retraction of his claim (of having an algorithm achieving the claimed bound) and how would I find such a claim? (Other than contacting the author, that one is obvious)
  2. If I'm unable to publish anything related to this, could/should I do anything?
  3. If I am able to publish something, how should I cover this issue? In particular, I'd like to be able to avoid comments such as "Haven't you read [extended abstract]? They've found a much better algorithm than yours!"

Also, the most of my doubts are related to the scientific status of the claim. Is it 'obvious' that it is poorly supported and possibly false, or does this require an extensive argument?

I suppose it isn't completely obvious, as the extended abstract is cited in a paper with the claimed bound (this paper doesn't actually use the bound, so there is no risk of 'error propagation' there), referring to a 'clever trick' that isn't explained in the extended abstract. (Perhaps the author of the citing paper had some private communication with the author of the extended abstract?) Of course, the citing author may knowingly be citing a vague claim, but let's apply Hanlon's razor here.

*: Technically, as this would be a conditional lower bound, it doesn't yield a formal contradiction. But such a bound would at least cast extreme skepticism on the claim from the extended abstract, comparable to when someone claims a resolution on P vs NP.

Improve this question

2 Answers 2

Reset to default
4

The obvious place to look for either a substantiation or a retraction of the extended abstract's claim wold be on the arXiv. Also, since the author is still active, you or your adviser could write to him and ask about the algorithm and its running time. If you still can't get the information you need, then I think you can publish your work and include, in a "Related Work" section of your paper, a citation of the extended abstract and a statement to the effect that you have been unable to find the details in the literature or to reproduce them yourself. Of course, if you manage to contradict the claim in the extended abstract (or to show that it would imply implausible things like P=NP), then you should say that.

Improve this answer
1
  • The extended abstract is from 1995 (a bit old, as I said). So I doubt I'll be finding anything on the arXiv (I tried searching, but I think I'm searching wrong). I did check dblp for publications of the same author, but I saw nothing related to the abstract. I'm a bit reluctant to contacting the author unless I'm researching with the intention of publishing, but I suppose that is the best once do have that intention.
    – Discrete lizard
    Commented Mar 16, 2018 at 10:32
2

If the author of the sketch is still in academia, you can email them and ask. They may confirm that their claim is wrong, or will direct you to the full algorithm or help you reconstruct it. Next step is to discuss the details of the reconstruction with someone (first choice is your supervisor) who may help you locate the mistake: of the original author or yours. In any case, from my experience, many times when my first impression was that someone is wrong, it was me who was wrong in the end.

Improve this answer
1
  • I do agree that it is hard to show that the author is wrong, as it is similar to showing Fermat's 'proof that doesn't fit in the margin' is wrong: I have no idea what his precise argument or algorithm is! (I mean, the claim could be true. I simply doubt that the author has shown that, because why wouldn't the author simply publish it?) Perhaps it would be most tactful to simply ask for an explanation of the algorithm.
    – Discrete lizard
    Commented Mar 16, 2018 at 10:35

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .