A simple plea to all computer scientists

July 25, 2007

I was trying to do a little background reading on a problem in complexity theory (this problem, to be precise), and I was dismayed to find myself thwarted by the unavailability of papers. Not being an academic type, I don’t have ready access to a research library. (I can, in theory, get papers from my local public library via inter-library loan, but it takes a couple of weeks. I can also drive to the nearest university that has a CS graduate program, but I’m not going to count that as “ready access”.) So I depend upon papers being available online, and a lot of researchers are very obliging in this regard. However, there are still a lot of exceptions.

For example, Richard Karp’s 1972 paper “Reducibility among combinatorial problems” [2] does not seem to be online. (By the way, it is of course possible that this or any the subsequent papers I mention are in fact online but I wasn’t thorough enough in my searches. Please let me know if this is the case.) This paper is mainly of historical interest at this point, but it was such an important paper that I’m really surprised by its absence.

Moving forward in time 16 years to 1988, we have another highly cited paper, “How easy is local search?” by Johnson, Papadimitriou and Yannakakis [1]. Again, given how many citations this paper has, I’m surprised no one has been moved to scan it and put it online. (Well, actually, someone has, and I’ll get to that in a moment.)

Going forward another 4 years to 1992 takes us to Woeginger and Yu’s paper “On the equal-subset-sum problem” [4]. Here we’re starting to get recent enough that the authors might still have the source versions of the paper in electronic form. Not to pick on anyone (especially since I’m a fan of his P vs. NP page), but why doesn’t Woeginger include this paper on his publications page?

Finally, for a recent example, we jump forward 11 years to 2003 for a paper by Kellerer, Mansini, Pferschy and Speranza [3]. Given the recent date of this paper I would have thought that it would be a matter of routine for the authors to upload a preprint of it to their web pages.

Out of a total of 9 papers I tried to locate online, I was unable to access 4 of them. The good news is that more than half of the papers were in fact freely available on the web. The bad news is the following: with the exception of the Karp paper, the others are in fact online and they’re for sale at Elsevier’s ScienceDirect. Now, I have nothing against capitalism, and I actually think it’s great that these articles are available for sale on an individual basis. But Elsevier charges $30 per article, and that is a bit steep for something that I might skim through once and then discard. Unfortunately, even after reading the abstracts it can be hard to tell which papers will turn out to be worth the expense and which ones won’t.

So, my simple request is that researchers take the time to upload papers to their web pages. I’m not sure what kinds of legal issues might be involved, but some of the articles that I did find online were also published in Elsevier journals, so I don’t think that copyright concerns are the main impediment. It may be more just a matter of developing the right mindset. So get those papers out there, and students and hobbyists everywhere will be grateful. (If copyright issues are the main problem, I’d like to hear more about that, too.)

1. D.S. Johnson, C.H. Papadimitriou and M. Yannakakis, How easy is local search?, J. Comput. System Sci. 37 (1988) 79-100.

2. R.M. Karp, Reducibility among combinatorial problems, in Complexity of Computer Computations, R.E. Miller and J.W. Thatcher (eds.), Plenum Press, New York (1972), 85-104.

3. H. Kellerer, R. Mansini, U. Pferschy and M.G. Speranza, An efficient fully polynomial approximation scheme for the Subset-Sum Problem, J. Comput. System Sci. 66 (2003) 349-370.

4. G.J. Woeginger and Z.L. Yu, On the equal-subset-sum problem, Inform. Proc. Letters 42 (1992) 299-302.


Evidently Shiva Kintali would also like to see more papers uploaded to their authors’ web pages, and he would like to see it done really, really quickly!

Commenter BarrosH pointed out to me that Karp’s paper can in fact be found online, at Papadimitriou’s Reading the Classics course.

posted in miscellany by Kurt

4 Comments to "A simple plea to all computer scientists"

  1. 知北遊 wrote:

    Christos H. Papadimitriou had given a course called “CS294: Reading the Classics”.http://www.cs.berkeley.edu/~christos/classics/cs298.htmlThere are e-prints of some classic papers, including “Reducibility among combinatorial problems.”I have a part-time job in university library. My job is about Document Delivery Service. Some great papers are requested copies very often, but, for academic publisher, it might be not worthy to scan old papers published decades ago.Besides, the frequent scanning or copying is really hurtful to the paper-print. I am convinced that digitalizing those classic papers is good for academia.

  2. Kurt wrote:

    Thanks for the pointer. I actually had a link to Papadimitriou’s Reading the Classics course in an old blog entry, but I didn’t think to check there.The funny thing about my search for the Karp paper was that I was over-specifying. By entering the full title, I was getting page after page of hits from other papers’ citation lists. On his web page, Papadimitriou simply referred to it as “Karp’s 1972 paper”, and sure enough if I do a Google search on “karp paper 1972″, it shows up half-way down the first page of results.

  3. Laura Dietz wrote:

    Kurt,I definitely agree with you that $30 is too much when you are not 100% sure the paper is of great value.I also see the point that there are publishers that need to make money. And AFAIK their terms do not permit the authors to put their PDFs online (although many researchers do it illegally).Of course we all hope that soon all publications are accessible for free. Until then I propose a different approach consisting of two ingredients.At ICML07 I published a paper about “Unsupervised Prediction of Citation Influences” (you can also try out the prototype here: http://www.mpi-inf.mpg.de/~dietz/citinf.html ). Given some seed publications it depicts the citation graph of papers that are strongly related, filtering out many citations / citings that are not really relevant. The second ingredient is that publishers (i.e. Nature) are thinking about the OTMI interface. This is an interface that basically gives access to the word histogram of the papers, which is fine for many machine learning methods (such as the Citation Influence Model), but does not reveal the human readable version, with which they earn money.Cheers,– Laura

  4. Kurt wrote:

    Laura,Thanks for the comment. Your citation influence work looks very interesting (from the point of view of a potential user of the system). I haven’t had a chance to download the viewer software yet, but I’ll be sure to do that when I have time. I hope you have success with the open source development, because it would be great to have this publicly available with a web-based front end on it.Of course, once the important pieces of research are identified, it would still be nice to have a lower price-point for purchasing articles…-Kurt

Powered by Wordpress and MySQL. Theme by Shlomi Noach, openark.org