28

I want to cite a theorem from a book written by two computer scientist that I consider to be influential and renowned. If you want the specifics, I want to cite Theorem 11.8 from the book Computational Complexity: A Modern Approach, by Sanjeev Arora & Boaz Barak. If it affects in any way, I am planning to submit this paper for a conference.

This theorem is stated on the book, however the proof is omitted since it is similar to another proof that is presented in the book. I keep wondering: should I include my own proof of this theorem or is it unnecessary? I could write the proof but I feel that it could be distracting and take space in a paper that will already have many short proofs (at least at this point in my research it seems that way). Additionally, I don't think someone would contest the validity of the theorem. On the other side, the result is vital to the content of the paper I am writing.

UPDATE: I should have mentioned before that in the book, three sources are cited for the theorem. However, when I read those sources, none of them state directly the theorem, even if they give the "building blocks" for proving it. I also tried searching for the same theorem in other sources and I found one in which it is proved, but it is stated in a way that could be confusing to read.

Improve this question
4
  • The theorem "Theorem 11.8 (Scaled-up PCP, [BFLS91, ALM+ 92, AS92]) PCP(poly(n), 1) = NEXP"? Have you checked if the proof was in one of the listed reference?
    – Clément
    Oct 25, 2022 at 15:10
  • 1
    Someone else asked about this. My response was "Based on those papers, the proof for the stronger result (which I need) can be derived, but neither the result or the proof are mentioned. I also looked for other papers in which the result could have been mentioned, but I did not find any". But yes, I agree the best thing to do in these scenarios is to look for the sources that are cited in the source one was reviewing. However, in my specific case, this did not work as expected.
    – Alonso Montero
    Oct 26, 2022 at 3:51
  • 2
    Ok, thanks. You could have included this discussion in your original question. I'm sorry tracking down this result turns out too be so difficult. There is sometimes a lot to learn in those "folkloric" theorems that are without proofs by simply writing a careful proof for the first time. Sometimes, the result is indeed derivable from other papers, but you have to fight with multiples notations.
    – Clément
    Oct 26, 2022 at 11:35
  • 2
    You are right about that: I should have updated my original question. I have just done that.
    – Alonso Montero
    Oct 26, 2022 at 16:18

3 Answers 3

Reset to default
33

You do not have an obligation to include a proof, and it might actually be to your detriment to do so, unless perhaps you believe that the textbook authors are severely mistaken when they claim the proof is similar to another proof that they did include and therefore is not necessary to explain in detail.

The point is that if the textbook authors’ assessment is correct, then you would be creating no meaningful new scientific knowledge by writing the proof in detail. Now, if you were writing an expository work and felt that writing out the proof would be of pedagogical value to students or researchers working in the field, then I would say it would be fine to write the proof. But in a conference paper, where the focus is on creation of new knowledge, including the proof of an already known result might actually make your paper seem less novel and draw criticism from the reviewers for rehashing standard ideas.

The one scenario where it would make sense to include the proof is if the textbook authors actually made the wrong call. If you work out the proof yourself and find that it requires substantially new or different ideas from what the textbook claimed, then it would make sense to write the proof in you conference paper. In that case, you should also point out that you are proving a result claimed in the textbook but explain that you are including the proof since it was in fact not as similar to the other proof as the textbook authors claimed. That implies that you are presenting new knowledge that you created, which actually should enhance the value of your paper as a research work.

Improve this answer
2
  • 13
    I agree with this answer. Just one comment: because by writing out the proof the OP would be claiming that it is not what the authors thought it was, he should take extra care to make sure that this claim is correct. This seems like a good thing to run by his advisor or other research mentor.
    – Pete L. Clark
    Oct 24, 2022 at 18:37
  • Would it be wrong for a paper to have links to proofs not considered the main idea of the paper (in say the references section).
    – Sidharth Ghoshal
    Oct 26, 2022 at 14:26
53

If we're looking at the same theorem, the theorem cites 3 papers where it is presumably proved. Why don't you cite those papers instead of citing the textbook?

This is in fact what you should do regardless of whether it is proved in a textbook or not. You presumably want to cite the textbook because it happens to be where you read about the theorem. But the reader doesn't care in the slightest about where you read about the theorem. They care about (i) who proved it and (ii) where they can find an accessible proof. If the textbook does not provide an accessible proof, then there is no reason to cite it instead of citing the original papers.

Edit: the OP has clarified in the comments that they "looked for the proof in those three sources but did not find it. Instead [they] found the proof for a weaker result. Based on those papers, the proof for the stronger result [...] can be derived, but neither the result or the proof are mentioned." Therefore this answer does not apply to the OP's situation and is superseded by the other answers.

Improve this answer
8
  • 10
    (+1) When I read the question I didn't try looking at the book (not my field or a book I have, probably not freely available to me), but I was going to suggest the OP put a little effort into seeing if a proof appears elsewhere, as I assumed the book did not cite anything relevant to the result (since if otherwise, I assumed the OP would not be asking here). That said, additionally citing the textbook also makes sense if the result itself and related matters are more completely discussed and/or more simply explained in the textbook than in the papers, something I would expect to be the case.
    – Dave L Renfro
    Oct 24, 2022 at 10:17
  • 11
    Perhaps we could take a page from our friends in law and say some thing "[textbook] citing [Papers 1,2,3]"? law.stackexchange.com/questions/85592/…
    – John Madden
    Oct 24, 2022 at 14:25
  • 9
    I should have commented this when I posted the question: I looked for the proof in those three sources but did not find it. Instead I found the proof for a weaker result: I was looking for PCP(poly(n), O(1)) = NEXP, and I found PCP(poly(n), poly(n)) = NEXP. Based on those papers, the proof for the stronger result (which I need) can be derived, but neither the result or the proof are mentioned. I also looked for other papers in which the result could have been mentioned, but I did not find any. However, I agree that, on the scenario I mentioned, this is the best answer.
    – Alonso Montero
    Oct 24, 2022 at 14:26
  • 1
    @JohnMadden I haven't seen anyone doing that in maths or CS papers, unless Wikipedia counts. I'd love it, as it makes it easier by far to build up a mental model of which things are worth reading, though it might not be the best idea to try to innovate citation styles. Most journals I know of have requirements.
    – wizzwizz4
    Oct 24, 2022 at 18:35
  • 5
    " If the textbook does not provide an accessible proof, then there is no reason to cite it instead of citing the original papers." --there could be a lot of reasons to cite the book anyway. If OP found the book useful, many will find it useful too. We often write: "See [1] and references therein"
    – yarchik
    Oct 24, 2022 at 19:40
23

If the theorem is central to your paper, I suggest you to put a proof in an appendix. In this way:

  1. Even though the proof is a straightforward adaptation of a book's proof, and no one would likely contest the theorem, it remains anyway documented for those who want to read it.
  2. It does not distract the reader from the main discourse.
Improve this answer
6
  • 6
    Massimo's suggestion is good, but in any case citing the theorem without proof is perfectly fine, too.
    – Federico Poloni
    Oct 24, 2022 at 7:37
  • 6
    CS conferences have pretty strict page limits, so it may be impractical to include the proof as an appendix.
    – Dan Romik
    Oct 24, 2022 at 17:13
  • 5
    In any case write down the proof! If the referees say that they would want to see the proof, you can easily add it if it is already written. Similarly, if you keep it as an appendix, and the referees want it removed, that will be also easy.
    – Kapil
    Oct 25, 2022 at 4:01
  • 4
    @DanRomik He can remove the appendix in the published version and put up an extended version on arXiv (maybe with a short remark in the conference version). I have seen this practise multiple times. Of course, first check if the conference allows informal publication on arXiv/preprint serves, but according to my experience in CS they almost always do and it is actually a common practise to have an arXiv version as well.
    – StefanH
    Oct 25, 2022 at 9:44
  • 3
    Some CS conferences don't include appendices in the page limit, so you could have arbitrarily long appendices. But (in my experience) these conferences emphasize that referees are not required to read appendices.
    – Andreas Blass
    Oct 27, 2022 at 0:08

You must log in to answer this question.

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