tag:blogger.com,1999:blog-3722233.post1802341424653728987..comments2024-03-02T02:08:38.816-06:00Comments on Computational Complexity: When do we stop giving the original reference?Lance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger7125tag:blogger.com,1999:blog-3722233.post-62846434745046465452016-01-29T13:46:32.519-06:002016-01-29T13:46:32.519-06:00THANKS, I have added the following refs to my pape...THANKS, I have added the following refs to my paper (on arXiv)<br />Karp- who proved { (G,k) : G is k-col } NPC<br />Lovasz and Stockmeyer who showed COL_3 is NPC.<br />As the paper title above indicates, Stockmeyer actually showed<br />Planar 3-col NPC.<br /><br />While these results are all well known and perhaps do not need<br />to be referenced (1) WHO did them is not that well known, and<br />(2) my paper was DIRECTLY on graph coloring and depended, contrasted, to prior work, so appropriate to give orig refs.GASARCHhttps://www.blogger.com/profile/06134382469361359081noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-82884884146592311752016-01-28T22:29:26.034-06:002016-01-28T22:29:26.034-06:00People in physics still keep citing the AdS/CFT pa...People in physics still keep citing the AdS/CFT paper from 1997 (see number 1. here: https://inspirehep.net/info/hep/stats/topcites/2014/alltime.html) when it is incredibly well-known and now has over 10k citations. If you don't know Madelcena's paper and are working on AdS/CFT, it's like working on quantum mechanics and not knowing what role Bohr played. (not sure that's an exact analogy, as QM is experimentally observed!)<br /><br />But that's not the worst: in biology people still cite a paper from the 1950's that invented a standard technique (see http://www.nature.com/news/the-top-100-papers-1.16224), which all students would know and study. It's not like we have to cite Newton and Leibniz when we use calculus...Unknownhttps://www.blogger.com/profile/09268986926485303519noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-40770615109663167072016-01-26T19:17:11.022-06:002016-01-26T19:17:11.022-06:00I Googled "Strong parsimonious reduction"...I Googled "Strong parsimonious reduction" and got nothing hence<br />this concept does not exist :-) Seriously, I think you mean<br />STRONG- if G has L 4-colorings then G' has L 3-colorings,<br />WEAK- if G has L 4-colorings then G' has f(L) 3-colorings<br />where f has some properties.<br />Anyway, I doubt my current reduction does, but I am sure it<br />can be modified to be weak pars.GASARCHhttps://www.blogger.com/profile/06134382469361359081noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-78531306562410314412016-01-26T13:15:57.108-06:002016-01-26T13:15:57.108-06:00Is your reduction parsimonious? (weakly or strongl...Is your reduction parsimonious? (weakly or strongly)Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-59394042436141585962016-01-25T13:14:59.058-06:002016-01-25T13:14:59.058-06:00I was under the impression that this was shown ind...I was under the impression that this was shown independently by Lovasz and Stockmeyer. <br /><br />L. Lovasz. Coverings and colorings of hypergraphs. In Proc. 4th Southeastern Conference on Combinatorics, Graph Theory, and Computing, Utilitas Mathematica Publishing, Winnipeg, pages 3--12, 1973.<br /><br />L. Stockmeyer. Planar 3-colorability is polynomial complete. ACM Sigact News, 5(3):19--25,1973.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-88669476468898740332016-01-25T09:08:44.611-06:002016-01-25T09:08:44.611-06:00On the one hand YES, refer to the original proof A...On the one hand YES, refer to the original proof AND the common proof AND point this out. On the other hand there is a limit to how far back you want to go with this.GASARCHhttps://www.blogger.com/profile/06134382469361359081noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-83121844361472249712016-01-25T08:25:01.155-06:002016-01-25T08:25:01.155-06:00Many times it happens the proof of a theorem commo...Many times it happens the proof of a theorem commonly known is different from the first publisher and remains unacknowledged. What is your opinion on that? Should a text book or paper refer to the paper that give the proof included for illustrative purposes?Anonymousnoreply@blogger.com