Monday, February 15, 2010

FOCS/STOC : What's the Big Deal?

As mentioned recently, the FOCS submission site is now up, and STOC acceptances have come out. Related blog posts have arrived, including an amusing one by Dick Lipton on if you could create a site that would automatically estimate the chances of your FOCS submission getting in.

So it seemed a good time to ask -- what's the big deal about FOCS/STOC?

FOCS/STOC are, I think, still generally thought of as theory's "flagship conferences." It's hard to get taken seriously as a theorist -- particularly when searching for your first (or even second) job -- without a reasonable number of FOCS/STOC papers under your belt. (SODA papers are, I think, now regarded as a reasonable substitute, but the lack of the heft of something in FOCS or STOC still stands out on a CV.)

But why?

When I was graduating, the colossuses that walked the earth were Jon Kleinberg and David Karger. If you look early in their careers, you'll see a steady and remarkable output of FOCS/STOC papers. (From 1995-1997, Jon had 6 STOC papers, 5 FOCS papers, and 2 SODA paper; from 1994-1996, David had 6 STOC paper, 2 FOCS papers, and 2 SODA papers.) These days, Jon's publications seemed focused on the KDD and WWW conferences, and maybe the EC conference. David, who has also always been eclectic in the most positive sense, publishes all over the place. You'll still see them appear in FOCS/STOC/SODA from time to time, certainly, but it's not where their energy seems to go. I don't find them any less colossal; they've just moved on to different things, different problems, that are generally not targeted to FOCS/STOC. Other examples include Bruce Maggs, who mostly does networking these days, and even Dick Karp, who -- while ever eclectic -- has published more in RECOMB than anywhere else the last decade. I could go on.

My point here is that many of the best theorists I know have, I would say, transcended FOCS/STOC. This does not mean there's not great stuff in FOCS/STOC; it just seems strange, given this, that these conferences are accorded such weight.

Perhaps, in fact, they're accorded less weight than I'm crediting them with these days. Certainly, the Innovations in Computer Science movement demonstrates some dissatisfaction with FOCS/STOC, and there are debates in subcommunities (SoCG, Crypto) about FOCS/STOC vs. the specialized conferences. It still seems to me, though, that FOCS/STOC is where most people would want their best theory results to appear, and it's still the lens through which fresh theory PhDs are viewed.

It seems to me that the theory community, as a whole, needs to think about FOCS/STOC/SODA and the other many conferences, and figure out what it wants them to me. FOCS and STOC haven't changed much over the years, and perhaps they've become just a bit too comfortable; the (theory) world around them has changed considerably, and it's not clear that they've adapted. Should they be the flagship conferences of theory, and if so, what does that mean, and how can they better fulfill that role? If they're not going to be the flagship conferences of theory -- which might be perfectly reasonable -- what is their role to be?


Anonymous said...

FOCS/STOC/ICS--I would like to see these as the major theory conferences. ICS is just one year but it promises to grow big. SODA/CCC/SOCG/Crypto I would like to consider them as specialized conferences on algorithms/complexity/comp-geometry/cryptography.

Anonymous said...

Your examples illustrate the breadth and power of theory and theoretical ideas but they are unconvincing in having any relevance to an assessment of FOCS/STOC/SODA.

You could have equally well chosen Christos Papadimitriou, Avi Wigderson, or Madhu Sudan, or any number of others whose contributions in the same time period have primarily been presented at FOCS/STOC but have had major impact both inside and outside the community.

I don't think that there is any controversy about what the scope of FOCS/STOC/SODA should be, which seems to be the focus of your post.

This is completely separate from the questions of their format/selectivity or their criteria for paper selection.

Anonymous said...

If you switch from field X to fields Y, Z, or W, this does not mean you have "transcended" X.

The fact that several people from X have moved to related fields Y,Z, or W, and now publish in different venues has no relevance to the question of which conferences in X are the important ones.

Suresh Venkatasubramanian said...

I think the technical term for this post is 'comment-trolling' :).

It's not clear to me that anything fundamental needs to change, and your examples of people who've "moved on" merely indicate people who are directing their energies in other realms. Nothing wrong with that, and it implies little about FOCS/STOC

I was just talking with a student about whether to send a paper to FOCS or to SODA, and I think I was able to articulate a reasonable difference in focus between the two. That's not a sign of a conference that's lost its way.

Geoff Knauth said...

Maybe they're leaving room in FOCS/STOC for a new generation, since FOCS/STOC is used to judge young theorists, their own positions are secure and they don't want to hog the platform. A similar discussion came up recently on the TYPES mailing list.

Anonymous said...

A conference that has a main purpose of judging people is ultimately empty. This isn't the olympics. Conferences are supposed to bring people with shared interests together. I think that as FOCS and STOC grow more ferociously competitive---after all, nobody is hiring theorists---their usefulness to the community will continue to decline.

Anonymous said...

What do people think about STOC/FOCS papers that, say, 5 years later, have < 5 citations? Does this mean that the committee made a mistake?

Michael Mitzenmacher said...

Suresh -- you've caught me, I'm comment-trolling, but with some points.

1) STOC/FOCS are, I think, still supposed to be the flagship conferences for theory. What does that mean these days? I don't think it's clear -- and it's something to talk about.

In other areas, most flagship conferences are either a) ridiculously competitive -- small numbers of papers, but a good part of the community shows up or b) big get-togethers -- hundreds of papers, high acceptance rates, and a good part of the community shows up (because they have a paper there). FOCS/STOC fit neither of these molds very well -- and their attendance has been pretty steady, perhaps with a small stagnation, over the past decade. Seems worth talking about.

2) As pointed out in other comments (and blog posts), STOC/FOCS have some perception issues. Some view them as "competitions" for up-and-comers. I've heard many say that they don't necessarily get the best papers in some strong subfields (covered by SoCG, Crypto, and others). Maybe such issues are unavoidable, but it again begs the question of what do we want FOCS/STOC to be, and are they meeting those goals?

Suresh Venkatasubramanian said...

"A conference that has a main purpose of judging people is ultimately empty"

well said !

Anonymous said...

What do people think about STOC/FOCS papers that, say, 5 years later, have < 5 citations? Does this mean that the committee made a mistake?

Having recently browsed the papers in the proceedings of STOC'95 and FOCS'95 it was surprising how strong and relevant the good papers are (even fifteen years later) and surprising to see how irrelevant, faddish and technically byzantine the bad papers were.

Anonymous said...

innovation of ... yeah rite ... how could u ever compare focs to some low level

Anonymous said...

As meetings, I don't find STOC/FOCS to be very satisfying - I prefer SODA both socially and intellectually. To answer the question "What's the big deal?" it is clear that a paper in STOC/FOCS is like a $100 bill - each individual values it because other people value it also. I would like STOC/FOCS to change - not only are they not very good as meetings, but they also damage various other conferences by creaming off all the best material. I'm not sure how change can be effected, however.

Mihai said...

The issue of citations is a bad match for STOC/FOCS. These conferences should accept progress on superhard questions (e.g. Ajtai's superlinear lower bound for branching programs), even though these papers will not really get cited much (improvements that generate citations don't come often). There are plenty of conferences making and following trends; STOC/FOCS should be about "foundations."

As for SODA, I would really like to count it as a top conference. But whenever I read the list of papers, I am left with an inescapable feeling of disappointment. It's not that papers are bad; they're just amazingly mediocre.

Anonymous said...

What are pros/cons of FOCS/STOC being a conference as opposed to a journal?

Anonymous said...

How can a paper be "foundational" and get few citations?

Anonymous said...

Mihai, I really do not like the way that you degrade SODA papers to upgrade your FOCS/STOC papers. The fact that you have more papers in FOCS/STOC really doesn't mean too much. Indeed it can be simply the case that you are working on some area without too much competition or active strong researchers. Your papers get accepted simply since a few people in this area who review your papers consider your papers better than theirs or at least want to keep their research area alive. It means your work is not necessarily very fundamental (and known within other areas of TCS) as you can see by searching your name in say Google Scholar. Your highest citation(including self-citations) is only 40 since 2004 (your first publication year) which is relatively low comparing to good papers on other TCS fields in the same era (which also supports the claim regarding a few people in your area). I think probably this is the reason that you do not like counting citations also.

Anonymous said...

@prev anonymous: Mihai works on difficult problems (and very few people are interested in that kind of stuff).
So, he does not believe in citations. Come on, some crappy systems paper has more citations (>30) than most fundamental results in TCS. This is no way implies that the highly cited papers are better.

Geoff Knauth said...

Speaking of Kleinberg, he's mentioned in this physics arXiv post in a timeline with Harvard economist Wassily Leontief who devised a sector valuation method in 1941 that won a Nobel prize in 1973 and which prefigures 1998 PageRank.

Matt Welsh said...

I can't speak for STOC and FOCS, but in the systems community I find the main value of the top-flight conferences to be about the set of people that go to the conference, not as much the papers themselves. Then again for grad students and junior faculty getting papers published in the "top" venues is clearly more important than for the senior folks. So perhaps you can think of STOC and FOCS as the best papers from those younger folks who have not yet "transcended" the venue.

Mihai said...

I actually have plenty of SODA papers (10, I believe), and I've attended nearly all SODAs since 2004. So I have no personal gain in bashing it.

As for whether my work is well known in the TCS sphere, you should ask me once (in person) what I think of the TCS community, and infer how much I care about their judgement.

Anonymous said...

Using publication venues to judge students is just like using their affiliations to judge them. The number of exceptions are too few (almost non-exist), and hence evaluating a paper or person based on details is just not worth it.

Piotr said...

I am not sure if this thread has already ended, or not, but here are my 3 cents anyway:

From the perspective of FOCS/STOC PCs that I participated in, I think that our overall role was quite simple: to accept the best, most interesting papers in theoretical computer science. So far so good.

Of course, in real life things are complicated by the following:

* the exact meaning of the above depends on how do we judge paper quality and what do we mean by theoretical computer science. These are good questions, with many possible answers. Ultimately, the answers come out as a superposition of PC members and sub-reviewers beliefs and opinions, which in turn reflect the value system of the conference community.

* it is not easy to judge paper quality. There are many different ways to do it; also, some factors (notably future impact) are random variables at evaluation time. As a result, PCs can and do occasionally screw up, sometimes badly. I would conjecture that the broader the scope is, the harder it gets.

* One can accept only what is submitted (at least, in our current model). Areas which do not typically submit to these conferences are under-represented and the conference role cannot be fulfilled in that regard.


Anonymous said...

Ultimately, the answers come out as a superposition of PC members and sub-reviewers beliefs and opinions, which in turn reflect the value system of the conference community.

I don't think it is quite that simple. If you are PC chair of a conference you are ultimately a steward of something that was created before you and will continue after. There might be many radical changes that for all I know everyone in the PC committee would agree to, yet I don't think it is the role of a PC chair to be a bull in the china shop.

As such changes happens slowly, and conferences end up being a compromise between what has been, what we want, and what can be achieved in incremental steps.