tag:blogger.com,1999:blog-3722233.post6226822728259857686..comments2024-06-15T07:55:26.321-05:00Comments on Computational Complexity: Re-request/when to include a known proof in a paper?Lance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger11125tag:blogger.com,1999:blog-3722233.post-51818365266646574952009-06-30T19:40:36.799-05:002009-06-30T19:40:36.799-05:00Further, errors with papers are almost never in th...<i>Further, errors with papers are almost never in these simple concrete results; on the contrary, one main cause of mistaken papers is to spend too much time giving overly detailed steps of the little results without really checking over the new ideas.<br /></i><br /><br />I disagree. Students or amateurs often fall into error by spending too much time on trivialities and skimming over the new ideas, but for professionals it's usually the opposite.<br /><br />In any case, the moral is clear: whatever you are tempted not to write up is the most likely place for an error to be hiding.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-89075981785403684772009-06-30T10:54:40.581-05:002009-06-30T10:54:40.581-05:00On the other hand, including these results makes i...<i>On the other hand, including these results makes it harder to read the paper because you have to dig through all the concrete results to find where real advances are.</i><br /><br />I think this is avoidable. Usually when I'm in such a situation, I put all these 'concrete results' in a section labeled "Preliminary Lemmas" or "Appendix" to draw the reader's attention away from them. So, the reader knows what's important, and for the curious reader who wants to understand all details doesn't see the 'trivial' proofs of the lemmas, they can flip to the appropriate section and read them.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-79363625116353342262009-06-30T09:19:34.972-05:002009-06-30T09:19:34.972-05:00I want to propose the opposite viewpoint to the ma...I want to propose the opposite viewpoint to the majority, that it frequently hurts to include simple proofs for completeness. "Concrete" statements from mathematics like this are, as Serge Lang used to say, "trivial or false". Simple sums, integrals, etc..., are things that the reader can usually check fairly easily. On the other hand, including these results makes it harder to read the paper because you have to dig through all the concrete results to find where real advances are. Further, errors with papers are almost never in these simple concrete results; on the contrary, one main cause of mistaken papers is to spend too much time giving overly detailed steps of the little results without really checking over the new ideas.Unknownhttps://www.blogger.com/profile/14738696573852659665noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-40597783883848488532009-06-30T03:38:35.152-05:002009-06-30T03:38:35.152-05:00there is no justification to publish something tha...there is no justification to publish something that was already published.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-64464195690169835122009-06-30T02:29:12.403-05:002009-06-30T02:29:12.403-05:00I don't know of a reference (besides some mate...I don't know of a reference (besides some material I've written myself), but the proofs I know are short enough that they should probably just be given.<br /><br />Here's one way to think about the result: if p(x) is a polynomial of degree n, the first result is equivalent to the statement that \sum p(k) x^k is a rational function with denominator (1 - x)^{n+1} and the second result can (I believe) be obtained by computing the coefficients in the partial fraction decomposition thereof.Qiaochu Yuanhttp://qchu.wordpress.com/noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-25339462119044488332009-06-29T21:04:09.329-05:002009-06-29T21:04:09.329-05:00This is part of what appendices are for.This is part of what appendices are for.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-63699227910921116492009-06-29T17:52:57.342-05:002009-06-29T17:52:57.342-05:00For a known result that you can find a proof somew...For a known result that you can find a proof somewhere in the literature, I think the decision should be similar to when to include a proof in a survey paper: yes if reading the proof teaches the reader something more than "this lemma is true", no if it doesn't. If it seems to be folklore but you can't track down a solid reference, though, probably best just to prove it with some disclaimer that you're not claiming any novelty for it.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-48554359314205579242009-06-29T17:51:35.137-05:002009-06-29T17:51:35.137-05:00Always there is an option to create a longer versi...<i>Always there is an option to create a longer version, with all the "well-known" details, on arXiv and give a link.<br /></i><br /><br />This is suboptimal, since it risks confusion between the two versions of the paper. (For example, someone may refer to the short version and think it contains material found only in the long version.) Instead of a longer version of the same paper, it should be a supplementary paper.<br /><br />As for references, Concrete Mathematics has a lot of information about this. It's not online (at least not legally), but it's definitely a better reference for most purposes than anything available online on this subject.<br /><br /><i>Never hurts to include a new or even an old proof with the disclaimer "for completeness".</i><br /><br />Occasionally it hurts, if the new proof is more contrived or complicated than the standard proofs, since that can give readers the wrong impression.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-46246880436574175322009-06-29T15:32:43.357-05:002009-06-29T15:32:43.357-05:00Always there is an option to create a longer versi...Always there is an option to create a longer version, with all the "well-known" details, on arXiv and give a link.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-17844878987305187482009-06-29T14:16:13.039-05:002009-06-29T14:16:13.039-05:00if there is a clean reference refer to it.if there is a clean reference refer to it.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-38663608941931962052009-06-29T11:51:12.672-05:002009-06-29T11:51:12.672-05:00Never hurts to include a new or even an old proof ...Never hurts to include a new or even an old proof with the disclaimer "for completeness".Lance Fortnowhttps://www.blogger.com/profile/06752030912874378610noreply@blogger.com