Should conference papers in computer science contain full proofs, and should these be checked by reviewers?

Question

I am a mathematician. In my subject, the normal means of disseminating research is to write it up with full and detailed proofs of the main results, which are then typically subjected to a rigourous peer-review process which can often take several years.

Much of my work, however, has an overlap with theoretical computer science, and I am often asked to referee articles sent to computer science conferences, which sometimes seem to me to have a slightly less rigourous review process. Therefore I have the following questions:

• As a reviewer, should I insist that CS conference papers contain full proofs of their main results?

• Should referees of conference papers actually check these proofs before accepting an article for publication?

These questions stem from a number of bad reviewing experiences I've had recently (as reviewer), in which I've rejected papers for basically a lack of rigour. One, which was submitted to a highly reputable conference, contained about ten additional pages of key proofs in a technical appendix, which was to be consulted ''at the reviewer's discretion'', and which would not have formed part of the final article. I rejected this on the basis that not only were the proofs themselves highly suspect (obviously grounds enough), but that the reader would never have had access to them and would have had to take everything on trust!

However, it turned out that I was the only reviewer who had these issues. The others were not only happy to have the main technical content of the paper relegated to a disposable appendix, but had not even bothered reading it! Eventually the paper did get rejected, but only after a fair amount of arguing on my part.

This is not by any means my only experience of this kind of attitude in computer science peer-reviewing (which would be frankly unthinkable in mathematics), but it illustrates the kind of problems I have as a reviewer.

I understand that there are cultural differences here, and that the speed of the conference system has its merits, so I am wondering whether I am being unfair to judge this system by the standards of rigour one normally expects from mathematical journals?

Answer 1

"Rigour" is a nice sounding word. I like the way it feels when I say it. But aside from making nice sounds, it has some issues:

... which are then typically subjected to a rigorous peer-review process which can often take several years.

Let's forget about how nice the word sounds and take a stab at a pros and cons analysis of having fast-to-write, fast-to-review, fast-to-publish, not-so-rigorous conference papers.

Pros:

• Time-to-publish is reduced (moving from a couple of years to a couple of months), meaning that results can have impact faster.
• Other authors will become aware that there are results in this area, rather than trying to prove results that have already been proven but are stuck in a multi-year peer-review process.
• Reviewers have to expend less effort reviewing less rigorous papers in a less rigorous way. They can use that excess effort elsewhere.
• Authors have to expend less effort to write less rigorous papers. They can use that excess effort elsewhere.
• The ability to write less rigorous papers does not preclude the possibility of writing a follow-up paper that is more rigorous.
• Authors have something to lose by publishing incorrect non-rigorous results: their reputation. (Not really a pro, rather more of a check-and-balance.)

Cons:

• Less rigorous papers may be more prone to being incorrect. This may lead to incorrect papers building on these results.
• Once a lack of rigour seeps in, one is on a slippery slope. Without any rigour, one is not proving anything. The whole thing become pointless.

I do not believe in some absolute notion of "rigour" for any non-trivial proof. I believe it's a relative term. One writes proofs for one's audience. The notion of "rigour" is thus community dependent. It is up to a community to decide what level of "rigour" is most appropriate for that community. If the "rigour" drops too low and incorrect results become a problem, the community should adjust. If the "rigour" becomes too high and reviewers have to spend months checking the dotted i's and crossed t's on long proofs for results that are simply not worth that effort, then that will carry its own costs, particularly in terms of the capacity of the community to do work, where diversity of work will inevitably become the first victim (the trend will be towards safe incremental papers).

Applying the standards of rigour from one community to another is, in my mind, thus inappropriate in and of itself. Rigour is, in my mind, not the goal. The goal, in my mind, is that the community be "productive" in whatever notions they and society deem productive (in the sense that society, after all, is funding this cost, and will not continue to fund this cost if the community is expending its capacity in pursuing rigour for rigour's sake).

tl;dr: I believe that "rigour" is a means, not an ends. I think if you really want to take exception to the lack of rigour in a community, you should show that the cons are outweighing the pros, which is to say you should highlight incorrect results and the time wasted by the community on following-up those incorrect results. Simply arguing that community A chooses to have less rigour than community B and thus community A is doing something wrong, is, in my mind, insufficient as an argument. You need to argue that the perceived lack of rigour is a problem.

Answer 2

A conference paper in TCS is usually best seen as an abstract or an advertisement of the full paper.

The full paper should appear in e.g. ArXiv before the conference, and it should eventually be published in a journal.

It is perfectly normal that there are some proofs that are in the appendix in the submitted version and entirely missing in the final conference version. The reader can find the omitted details in ArXiv.

Answer 3

What you're describing is quite common. Page limit in a conference can be, say, 15 pages, and in this case there's no way to include a 10 page proof in the main text. It is also likely that the proof is not seen as the main contribution of the paper.

Proceedings of the conference will indeed not include the appendices, but often authors upload papers to their web-pages, to their institutions' repositories, etc, so the proofs may be eventually accessible to the readers.