A simple plea to all computer scientists

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.

Updates

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.

More Open Problems

Here I was just mentioning open problems a few days ago, and in a little example of synchronicity there have been a couple of recent posts on other blogs describing instances of open problems.

Ken Regan, guest posting at Computational Complexity, poses a problem asking how many gates are required in a circuit which computes a 'garbage collection' function. The motivation behind the problem (speaking very generally) is that before we can even begin to think about the likes of P vs. NP, we ought to be developing techniques for proving super-linear lower bounds on much simpler problems.

Mark Chu-Carroll at Good Math, Bad Math describes an open problem in graph theory called the reconstruction conjecture. This conjecture postulates that any finite graph with at least 3 vertices is uniquely determined (up to isomorphism) by its vertex-deleted subgraphs. Mark has been doing a nice series of posts on the basics of graph theory leading up to this one.

I've never been good at thinking about computation in terms of circuits, and likewise graphs are baffling to me (these facts are perhaps not unrelated), so I'm not going to be losing any sleep over either of these problems. However, that pigeonhole subset-sum problem over at the Open Problem Garden has really gotten under my skin. I'm beginning to think that maybe having a collection of open problems isn't such a good idea--it's a great time sink that will keep you from doing all the things you're supposed to be doing!

Update:

7/13/07: Bill Gasarch at Computational Complexity has a post plugging the Open Problem Garden. Maybe we have a little momentum building now...

7/17/07: And here is one more open problem post: Michael Mitzenmacher asks for codes for a Poisson-repeat channel over at My Biased Coin.

Carnival of Mathematics

I was just thinking to myself that it's been a long time since I've seen a new Carnival of Mathematics, and sure enough when I checked the calendar I found that the 11th edition is now up at Grey Matters. Hmmm, none of the math/cs blogs I read regularly posted any announcements about this; how am I supposed to remember these dates on my own? Maybe everyone is on vacation this week.

Perhaps it's just the summer doldrums, but this edition of the carnival seems a bit thin. There was a little bit of discussion back in the 10th edition about whether it might make sense to split into two separate carnivals: one for math ed and one for college and research level math. However, the current edition is almost all math ed, so perhaps the carnival will just evolve in that direction on its own. (There were also a couple of entries that really left me wondering what the authors were smoking, but that's another matter.)

There was one entry that struck me as being worth mentioning, though. John Armstrong at The Unapologetic Mathematician writes about categorification: the process of recasting a mathematical abstraction into the language of category theory, as a means of solidifying one's understanding of the topic. He gives some simple examples expressing addition and multiplication in terms of set operations, and reinterpreting the results in terms of category theory. As someone who doesn't know anything about category theory, I find this both intriguing and mystifying. He concludes his post with the adage, "If you want to understand something, try to categorify it!" I think that I first need to understand categories, and Armstrong has a series of posts on the basics of category theory that might help me in that regard.

While we're on the topic (sort of), I wonder if it would be worthwhile to try to split off the TCS-related posts from the Carnival of Mathematics into their own carnival? That might sound a little strange seeing as how there were exactly zero computer science posts in this edition, but I'm thinking that having our own carnival would encourage more submissions. Or is the TCS blogosphere so small (and we already read each other's blogs anyway) that having a carnival would be superfluous?

Open Problems

One topic that comes up on a regular basis is the question of how to come up with open problems that might be suitable for tackling. Of course everyone knows about P vs. NP, and like Fermat's Last Theorem in number theory, this problem can serve as motivation for studying the foundations of computational complexity. However, as was the case with FLT, it is not a problem that a student would hope to make any real progress against. One difficulty with identifying problems that are hard enough to be interesting, but not so hard as to be hopeless, is that the people who are familiar with such problems might be reluctant to advertise them--they understandably might want to tackle the problems themselves first, or in the case of faculty, to give the problems to their students to work on.

So it was especially nice to learn (via David Eppstein) about the Open Problem Garden created by Matt DeVos and Robert Šámal. The Garden is a wiki-style repository of open problems from math and computer science, so anyone can register and contribute their own entries. Problems are categorized by subject (graph theory, combinatorics, etc.), and rated according to importance. Problems are not rated for difficulty per se, but there is a yes/no indicator for whether the problem might be suitable for an undergraduate student. It looks like the database was preloaded with the problems from Bojan Mohar's Problem of the month page, so it is currently heavily weighted toward graph theory. I'm really hoping that as time goes on, people in the TCS community will use this repository to store their own open problems.

There is as of this writing a single entry in the TCS subject category: Subset-sums equality. This search variant on the NP-complete decision problem SUBSET-SUM is one which I haven't seen before. Unfortunately, the entry does not currently contain much background or any references, so perhaps if someone reading this is in the know, they could flesh out the entry a bit. (A quick search turns up this article on finding approximate solutions to the problem.)

While I'm searching around, perhaps I should look for other sources of open problems... Unfortunately, a lot of the hits returned by Google are pages describing P vs. NP and not much more (including, surprisingly, this Wikipedia article). Open problems have been discussed on at least a couple of occasions on the Computational Complexity blog, here and here. In fact, in the comments to that second post, Matt DeVos puts in a plug for the Open Problem Garden (which was in beta at the time). That was back in March, and evidently no one in the meantime has been sufficiently motivated to add any additional TCS open problems. Pity, that.

Finally, for something of a slightly different flavor, here is David Johnson's Challenges for Theoretical Computer Science. Instead of a list of conjectures to be proven, this is a list of broad challenges for computer science, perhaps reminiscent of David Hilbert's list of problems for mathematics.