27

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?

  • 3
    -1 Either the proofs were wrong or not. I do not understand what "highly suspect" means. Right now your question seems like a rant about CS vs math. Voted to close. – Alexandros Aug 9 '16 at 13:27
  • 18
    Well a proof can be wrong, it can also be incomplete, it can be lots of things that prevent it from being a proper proof. But that was hardly the point I'm trying to make. The question I'm asking is very clearly stated. – Rhidian Aug 9 '16 at 13:54
  • 4
    "Should there be rigour?" Of course it should. "Is there rigour in highly reputed TCS conferences?". Of course there is. "Being a reviewer limited n times proves that there is not rigour ?" Of course not. This is the textbook definition of an incomplete proof. – Alexandros Aug 9 '16 at 13:58
  • 11
    Again, none of these were points that I was trying to make. – Rhidian Aug 9 '16 at 14:01
  • 8
    OP's question is a matter of intense debate and disagreement among (at least a subset of) the theoretical computer science research community. I fully support your argument for rejection on the grounds that the proofs would not be available to the reader, but this is a minority opinion. – JeffE Aug 10 '16 at 3:33
10

"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.

3

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.

  • 3
    and it should eventually be published in a journal. On this site, you will find some rather interesting discussion on conference papers vs. journal papers in the TCS field, and which is the norm, more prestigious, etc. (e.g., here and there). When you say "should eventually be published," do you mean it is expected, or it would be nice but not "required?" – Mad Jack Aug 9 '16 at 17:03
  • @MadJack If a conference paper refers to a full version, then it is certainly expected that the full version would one day appear somewhere. Of course it does not always happen, but in the long term I think a pretty good fraction of papers that have had long-term impact have also eventually appeared in journals. (Not because journals are prestigious, but because it is a good scientific practice.) – Jukka Suomela Aug 9 '16 at 20:25
  • I see, thanks. Regarding the main question in this thread: generally speaking, if authors of a TCS conference paper cite their, e.g., arXiv paper, which contains more rigor, proofs, etc., would you say that it is common for conference referees to consult the arXiv paper and ensure it's correctness prior to recommending acceptance (assuming the conference paper has no other show-stopping flaws)? – Mad Jack Aug 10 '16 at 0:02
  • 3
    While there is a cultural expectation that TCS conference papers will eventually appear in full on the arXiv or in journals, it is a weak expectation. In practice, a significant fraction (if not a majority) of TCS conference papers do not eventually appear in full on the arXiv or in journals. – JeffE Aug 10 '16 at 3:28
  • 1
    Dentists expect their patients to floss twice a day. – JeffE Aug 10 '16 at 3:35
0

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.

  • 2
    Please allow me to make some comments. (1) It is also likely that the proof is not seen as the main contribution of the paper. Then how do we verify the main contribution of the paper? (2) so the proofs may be eventually accessible to the readers. The OP is asking Should conference papers in computer science contain full proofs, and should these be checked by reviewers? not whether the proof is accessible. – scaaahu Aug 10 '16 at 6:37
  • 2
    The silence I am witnessing on this thread related to the following issue is deafening. 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. — I get the conference-paper-page-limit problem. However, if a more detailed paper exists somewhere (arXiv, personal webpage, etc.), is it common practice that the conference referees will actually look at it to ensure correctness of the conference paper results? – Mad Jack Aug 10 '16 at 20:13
  • 1
    @scaaahu Should the papers also contain source code and datasets? In many cases, you cannot verify the main contribution without them. – Jouni Sirén Aug 10 '16 at 21:57
  • @JouniSirén In some purely theoretical computer science papers, say a paper concerning Turing computability, there is no source code or dataset associated with it, only mathematical proofs would be at issue. I was talking about that case. – scaaahu Aug 11 '16 at 3:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.