Wednesday, May 21, 2008

The "Conceptual" Debate

I'm not at STOC, but I see the debate about "conceptual" papers appeared again at the business meeting, as it rightly should. It's obviously an area where there's disagreement, in terms of whether there is an actual problem currently, as well as what to do about it. It's something that, as a community, we need to talk and think about.

Rather than engage in debate specifics, let me suggest (yet another) way of thinking about the problem. As a community, we need to think in terms of our field having a regular check-up. Not that we think there's any emergency, but as a community we act like our primary care physician and look at where we are, and make sure that problems that need to be looked into are being looked into.

As part of that check-up, I think it's reasonable to ask if our community has produced a healthy number of good concepts. (This, to me, is the heart of the debate.) At the end of the day, in many important ways (including NSF funding, prestige in comparison with other areas of CS, possibly even job production) the production of concepts is at least one significant way in which we'll be judged. Arguably, it's the most important way; certainly externally to CS, and to large part internally to CS, and even within TCS, people remember and latch onto concepts more than technical details.

I think the vision workshop before STOC played something of this role -- transforming concepts into nuggets for an NSF-style audience -- albeit looking more forward that backward. As a community, though, perhaps we need some metrics to go along with these checkups. We need some goals to let us know if we're being successful, and numbers to let us know if we're achieving those goals.

My bias is that one way to see if we're succeeding in concept production is to consider how much our work is used (measured say by citations) outside of TCS. If we come up with a good concept, often it will show by being spread along outside of our limited community. I know that's just one metric, but it's one I like. We should regularly see how FOCS/STOC conferences are doing in terms of the concepts making their way into other communities, and compare it to other theory conferences, and other conferences in related fields (say, with the International Symposium on Information Theory). We should see which theory papers become highly cited outside TCS and, when they don't appear in FOCS/STOC, we should question why, since FOCS/STOC are supposed to be our premier conferences.

And, personally, I think we need to think of other check-up items we ought to be looking into. (Example: how is hiring going in TCS? How many people are leaving the area after getting their Ph.D.s? Why?) Overall, I think these debates and discussions are quite healthy for the community, and we actually need more of them.


Anonymous said...

I'll comment on this here rather than at your link. It's interesting that the game theory crowd went 5/13. Do you champion them as collectively conceptual or technical?

I had the occasion to read a couple of papers by one of the [name withheld] esteemed members of the algorithmic game theory crowd. I read and re-read the paper, and started to work on the details that weren't in it.

I got confused and thought, "This must be very technical," so I dug into the primary references. They were much more satisfying and made a lot more sense, and I realized, "Ah yes, with a wave of the hand, a result."

[a result which makes a lot of intuitive, conceptual, sense, but isn't very well founded in its principles, used categorically terrible examples to illustrate its points, misses the whole point of the approach, and segues to a paper that is probably more elegantly framed as a metric embedding (I have to find out if that means what I think it does, and think to see if that is right)].

Michael Mitzenmacher said...

I think the "game theory" area is wide enough and as a whole novel enough to CS that there are both conceptual and technical papers in the area. And please keep in mind I think both conceptual and technical papers are valuable.

Anonymous said...

One should also keep in mind that there is a risk of becoming too "trendy" if we are not careful in how "conceptual" papers are treated. For example, there was a time when algorithmic game theory was particularly hot and it seemed that any paper on the topic was accepted; the same thing happened for extractors for a couple of years as well.

Michael Mitzenmacher said...

Anon 3 -- I don't understand, is this a complaint against conceptual papers or technical papers? Because my perception is that there are commonly technical papers accepted to FOCS/STOC in trendy (and even non-trendy) areas where it seems the main reason for acceptance is that it improves on a previous result and is mathematically challenging, even though there's not really a new mathematical technique nor a concrete motivation other than that there were previous papers on the topic.

Anonymous said...

I am not convinced that impact on other communities should be a metric for FOCS/STOC. I agree that it should be a metric for the TCS community at large, at it moments of self reflection, but FOCS/STOC should be concerned with impact on theory. One may even argue that papers that show the potential practicality of theoretical ideas should be published in more accessible conferences. Furthermore, I'm not sure this property could be evaluated effectively. I can't name many theory papers which are cited often (and correctly!) in the non-theory parts of cs, nor do I understand how a paper achieves this status.

Michael Mitzenmacher said...

Anon 5: I certainly think the points you raise are open for debate -- perhaps FOCS/STOC isn't the right place for emphasizing the theory-practice connection, as long as, as a community, we devote appropriate resources to that priority. However, I don't get:

I can't name many theory papers which are cited often (and correctly!) in the non-theory parts of cs, nor do I understand how a paper achieves this status.

Start with people who work across boundaries, and look at their papers. (And notice that, generally, they do spend some time talking with people and promoting their work with people outside of theory.) Me, Joan Feigenbaum, Piotr Indyk, Muthu Muthukrishan, Ashish Goel, Jon Kleinberg, David Karger... I'm just getting started, it's a reasonable list.

Anonymous said...

The 'consistent hashing' paper is what I had in mind when I said I don't understand how a paper achieves a status of being quoted often outside theory.

But I get your point :), still most of the more influential papers were published outside STOC/FOCS and that's no coincidence. The two main exceptions that I can think of are Kleinberg's papers (which shows that significant conceptual contributions are accepted) and the locality sensitive hashing papers which are cited often but typically not correctly.