Thursday, March 13, 2008

Conferences and Correctness

A post by Mihai Patrascu brought up the difficult issue of how to deal with papers that may or may not be correct when on a program committee. This is, clearly, a difficult question, and can lead to tremendous difficulties, as it is often not a simple task to determine correctness.

One approach is when an issue arises to inform the author(s) and ask them to clear up the issue. I recommend this, but it is not always functional; there may be disagreements between the author and the reviewers, and there is usually a limited amount of time to settle the problem.

Also, this seems to set up an onus on the author that may be unfair: you must convince us (outside what you've already written) that your proofs are correct. Now, that might not sound like an unfair onus, but for a difficult proof it may be very challenging, particularly since initially all that's been asked for (in most conferences) is a 10 page abstract and not the "final" version. Moreover, it's unfair because it's not something you're really asking of all the other authors. Sure, nominally you are, but papers with bugs get through often enough. Sometimes we make mistakes, and arguably there is some unfairness in a policy that insists that suspicious paper X must now be proven until all reviewers are fully satisfied while papers that didn't raise suspicions pass right on through.

As I've mentioned, I think the main job of the PC is to prioritize what papers get in a conference, and a secondary job is to give feedback to the authors. As part of that job, naturally, we want to throw out papers that are wrong and let the authors know about mistakes. But my argument is that conferences (and PCs) are not designed to accurately tell if papers are completely correct. If they were, I wouldn't have 45 papers to consider in a bit over a month, and I wouldn't be given papers on topics like quantum computing to judge. Ensuring correctness is nominally what journals are for, and that's why (in general) journal articles can take more time to review, and why one seeks experts for reviewing.

I'm not sure what a good solution is, and I'm not advocating blindly giving benefit of the doubt to papers that appear wrong. But there should be a high-level understanding that the conference procedure is inherently noisy. Mistaken proofs might be published. Perhaps the problem we should turn our attention to is how, as a community, we handle these errors, including arranging for such errors to be corrected or noted (by the authors or otherwise) in an appropriate fashion.


asarwate said...

On the other end are information theory conferences -- ISIT is huge and has a large acceptance rate, but the point of the conference is to essentially issue an advertisement for some journal paper that you have submitted or will be shortly submitting.

The result of this is that journal papers are everything, and while it's nice to send papers to conferences, it's not the important part of your CV, even as a student.

I think you can't address the issue of PCs guaranteeing correctness without addressing the reason for extreme selectivity at theaconference. If the PC's role is largely curatorial, is having a lot of papers in FOCS/STOC/SODA an indication of how trendy your research is?

Luca said...

Another scenario to consider: suppose a paper with a serious bug, which looked suspicious to the reviewers, gets into a conference because the PC thinks it should have the "benefit of the doubt." At the next conference, a paper is submitted claiming to point out the error and to give a correct proof.

The new paper, however, does not give a concrete counterexample, but rather an explanation of why there is a gap; and the new proof is very complicated. The new paper looks suspicious to some reviewers. Now do you give the benefit of the doubt to the new paper?

Arvind Narayanan said...

First, I don't think it's unfair. The authors might even be happy to work with the reviewers to explain the proof; after all, if the paper gets published, this is something they will need to do many times over.

But the solution to me is clear: allow authors to submit a video explaining proofs that they think are tricky. The reviewers are of course not required to look at them, but it gives the PC the moral ground to reject a suspicious looking paper if there is no accompanying video. Authors submitting a video slightly decrease the odds of getting rejected because of a complicated proof.

I believe a similar idea has been tossed around before, and there were objections of a fundamental nature to any sort of non-paper submission. I believe those don't apply here since the video doesn't make or break the paper. In any case, it's no use pretending that we live in some sort of idealized world where participants don't have material manifestations, or that anything human needs to be taken out of the process.

Michael Mitzenmacher said...

Luca -- hey, were we on the same PC where the scenario you're describing occurred? :)

Personally, I think having both papers published would benefit the community more than just the first -- at least then it might attract enough attention to the issue to have people resolve the problem, instead of just letting it sit there. And if the first paper was wrong, how else does one get a correct proof out?

Michael Mitzenmacher said...

Arvind -- since trickiness is in the eye of the beholder (reviewer), I think you're saying everyone needs to submit a video. People can have different opinions on whether that's a good idea or not, but I'd personally be against it.

asarwate said...

I think the decision to make in these cases would be clearer if the purpose of the conference is clear -- is the PC looking for novelty and plausibility (something to spark discussion) or breadth ad correctness (something to give a snapshot of the "state of knowledge"), or something else?

An interesting but ultimately flawed result, if presented, may lead to a real solution.

What about having, in the proceedings (or somewhere else) a response/critique format like they have in some statistics journals? A reviewer who really takes issue with some bug can have a formal rider on the paper in the proceedings (but not a presentation, clearly). That would require them to de-anonymize themselves of course.

Anonymous said...

But my argument is that conferences (and PCs) are not designed to accurately tell if papers are completely correct.

Problem is that we act as if they were. Just try to publish a correct and complete proof of a result that has been incorrectly claimed in the past (or claimed without anything approaching a complete proof). I can think of several surgical procedures that would be considered a more pleasant experience.

Mihai said...

My simple suggestion is to allow papers to appear in conferences after being accepted (past round-1) to a journal. Of course, we shouldn't require this for most papers, as that would destroy the rather wonderful dynamic environment that we have now. But in difficult cases, I think doing this covers a crack in the system.

Anonymous said...

Seems to me there should be an onus on the author to write a clear proof to begin with. Do we really want to accept papers where the proof is incomprehensible, regardless of whether the theorem is ultimately correct or not?

On another note, people seem to assume that journals are the answer. Come on, you've never seen journal papers with bugs?

Anonymous said...

I disagree that PCs have no responsibility w.r.t. correctness. By that standard the Complexity PC this year might have accepted both the paper claiming a proof that P != NP and the paper claiming an efficient (linear time?) algorithm for SAT since, obviously, the problems are of sufficient importance!

Once you accept this level of filtering, where do you draw the line? Certainly, the arguments had better be plausible. The more suspicious they are of correctness, the more careful a PC should be, and the same probably should apply based on how big the claims are.
That's why we often allow appendices or longer versions than will appear to let the PC have a chance to verify claims if they want to.

Final responsibility lies with the authors but out of fairness the PC ought to make some effort to check claims.

Michael Mitzenmacher said...


I'm certainly not suggesting that PCs abdicate their role in trying to assure correctness of what gets published (I hope that was clear in my post). Surely it should keep out things that seem clearly wrong. But when one reviewer says they doubt the argument (a situation which comes up not infrequently), and the question doesn't seem to have a simple resolution, what does a PC do?

Luca said...

With my hypothetical example I wanted to point out that this "giving the benefit of the doubt" policy can suffer from diagonalization.

Do you give the benefit of the doubt to a paper that contradicts another paper to which the benefit of the doubt was previously given? I guess the answer has to be yes, but imagine having two published, and possibly incorrect, papers claiming results at odds with each other.

It's enough to kill whatever subfields they are about, because who wants to use results from those papers (at the risk of basing his own work on incorrect results), or, even worse, come up with a third proof?

I think it makes sense that PCs are careful with papers for which reviewers are doubt. The worse that can happen is that the paper is rejected even though it was right, and the author resubmits a better version, which is hardly a bad thing.

Luca Aceto said...

I think it makes sense that PCs are careful with papers for which reviewers are doubt. The worse that can happen is that the paper is rejected even though it was right, and the author resubmits a better version, which is hardly a bad thing.

I could not agree more. If, during a PC meeting, a referee claims that a paper contains a serious mistake or that (s)he cannot see why some result is correct, then the other reviewers for that paper should make some effort to check that claim. In case the issue cannot be cleared up for lack of sufficient detail in the submission, I think that the author should be asked for full details of the proof. If the PC cannot convince itself that the result "smells right", then the paper should not be selected for presentation at the conference.

If the claimed result turns out to be correct, the author will publish it somewhere else, after having spent more time and care in writing up its proof so that an expert can vouch for its correctness. Publishing a better conference paper will benefit both the author and the research community.