Continuing from my last "controversial" post, David Karger offered the following long comment, turned into a guest post:
I wanted to post a comment on Mike's FOCS/STOC post, but fittingly for one of the dinosaurs he mentioned it was too big for the comment length limit. Mike's been kind enough to offer to post my comment as a guest post instead.
Mike's question is one I care about a lot. I still respect theory and do work in it, but as Michael says, much of my attention has been drawn into other areas. Many of them have absolutely nothing to do with theory (see last year's ethnographic study of people's use of pencil and paper for notetaking in TOIS 2009 or our AJAX-flavored interface for visualizing and navigating semistructured data in UIST 2009).
But always, some of my favorite projects are where theory provides the answers to problems that matter in other areas. We just published a paper in Nature Genetics that used some simple applications of max-flow to help biologists visualize the "important" influences in biological netwoks (we didn't need to find NP-hard integral solutions because the scientists wanted to see all the possibilities in the mix). Before that, we applied a beautiful JACM paper of Alon etc., on finding longish paths in a graph, to a problem in natural language processing---designing a procedure to figure out a best selection and ordering of words for a machine-generated summary of a machine-generated document---and published a paper at NAACL, a linguistics conference.. I still remember thinking, when I first read Alon et al., that it was one of the prettiest and cleverest ideas I'd seen in a while, but that it would never be useful for anything practical. Ironically, when my colleague Regina Barzilay outlined the language problem to me, it was exactly the Alon problem with no need for translation; my entire contribution was to know that a solution existed (and thus keep up theoreticians' reputation for smart enough to solve any problem instantly).
Other applications of theory to practice have required more work. Mike recently wrote about our paper showing how to design "network codes" for efficient multicast; the core insight of this work was to connect it to the beautiful results that we all study in randomized algorithms courses, on finding perfect matchings by placing random numbers in a graph's Tutte Matrix. Most substantially, our line of work that led to Danny Lewin and Tom Leighton's founding of Akamai begin with a study in STOC of some theoretical problems around handling flash crowds on the internet, and also generated a whole line of research on building robust and scalable peer-to-peer systems.
With the exception of the first paper on consistent hashing, none of this work has appeared in theory conferences. I think there are several reasons for this. Selfishly, for the author it is much more fun (and valuable in generating future research leads) to present the work at non-theory conferences. It holds the same attraction as tourism, going to strange new places and learning new things from the experience. There's also vanity---the allure of being an exotic theoretician among practitioners instead of one of a crowd of better theoreticians than you. Most important, if you want your work to have an impact on the applied areas, you have to publish in their conferences so they'll pay attention---they don't read STOC/FOCS.
But the second reason is more problematic. Many theoreticians would tell you (some have certainly told me) that the above papers are "not theory". That by dint of their having applications, they are no longer suitable for STOC/FOCS. That these papers have a different home, and FOCS/STOC should be reserved for "pure" (i.e. homeless) theory research. I've been on STOC/FOCS PCs that have rejected nice applications of theory on the grounds that the theory part was too elementary.
In part they are right. The biology and NLP papers I mentioned above did not prove any new theorems. But the omission of applications papers from STOC/FOCS means that theory community is failing to celebrate one of its greatest contributions! There's always been a divide in the theory community between those who are enamored of theory problems that help them understand the deep nature of the universe and computation (scientist/mathematicians) and those who see theory as a way of thinking about solving concrete computational problems that often emerge from other areas (engineers). I think that STOC/FOCS is making a mistake by focusing too much on the science to the exclusion of the engineering.
I would really like to see more "applied algorithms" papers appearing at STOC and FOCS. These are likely papers that have not made a major theoretical advance, but rather have synthesized our existing theory knowledge into a solution to someone's particular problem. These papers are just as important to see as the ones that advance theory; they represent one of the major justifications for doing theory in the first place.
I haven't mentioned SODA yet. That is a conference that was founded in part to attract these kinds of applications papers. But at the same time it was founded to attract more of the theoretical discrete math community, and the multitude of targets makes the outcome diffuse. Possibly as a result, SODA doesn't have the stature as STOC/FOCS; I'd like to see applied algorithms appearing at our flagship conferences.
Even if the STOC/FOCS community decides to do this, we still have to deal with what I said at the beginning, that the applied conferences are often more attractive for this kind of theory. You might say "fine, if that's what they want, there's no problem." But I think there is a problem: our community, and in particular our theory graduate students are not being exposed to this important branch of theoretical computer science.
The best solution I can think of is to allow repeat submission. That is, to let the paper appear first in the applied conference, then at STOC/FOCS. Almost by definition, these two venues will not have a lot of overlap, so I really don't see a downside to presenting such a paper at both of them. There are two ways to get this by the copyright police. The first is to accept the paper for presentation but publish only a reference to it in the proceedings. The second is to ask the author to write a new version of the paper aimed at a theory audience. Given the different audience, the paper is likely to be quite different.