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:
- 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)
- If I'm unable to publish anything related to this, could/should I do anything?
- 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.