STOC notes

It looks like we ended up with about 329 submissions. (Hopefully that won't change much at this point.) That's between 40-50 papers per PC member at 3 reviews per paper.

Thanks to everyone who withdrew the papers they weren't submitting. Otherwise, I had to go through and withdraw them manually myself.

Thanks to Shai Halevi for continuing to help me with the reviewing system.

Yes, I did get mail from about 10 people who hadn't known they'd need to file an abstract the week before, and I accommodated them. I think this should become a standard and everyone should get used to it. Again, keep in mind there's 40-50 papers per PC member; anything that makes their work easier is a good thing. (And Shai's interface for choosing preferences lets you see a paper's abstract pop up with a mouse rollover, so it's really nice to have abstracts early!)

Assuming things continue to go well, expect e-mail from PC members asking for you to handle a subreview before you head off for Thanksgiving....

Technical Depth vs. Novelty vs. Potential Impact

Let's say you're the PC chair for a major (theory) conference, about to give instructions to the committee. The standard way to judge a paper in theory is primarily based on its technical depth, but there's certainly a push in the community (and, arguably, from our funders the NSF) to consider other aspects, including novelty (could this start a new research direction, or give us a new way to look at things) and potential impact (might people actually use these ideas)? How, exactly, should you instruct the PC to weight these various factors?

Conceivably, we could set up the reviews to have a score for each factor. For example, I'm on the PC for NSDI, a systems conference, and we have to give scores for Overall Merit, Technical Merit, Longevity (= how important will this work be over time), Novelty, and Writing (as if that score matters :) ). Personally, I don't like this, and I'm not intending to do it for STOC. It's more pain for me as a reviewer without I think giving meaningful information to the authors (instead of spending time trying to decide if a paper is a 2 or 3 in terms of novelty, let's give another comment in the review text!), and when it comes time to make the decisions, I'm not really sure what I'm supposed to be (Pareto-)optimizing in this multidimensional space.

I'm a big believer, for conferences, in the "simple" method, as I've said before -- papers just get a score from 1-5, under the following scheme:

1: Bottom 1/2 of submissions.

2: Top 1/2 but not top 1/3 of submissions.

3: Top 1/3 but not top 1/5 of submissions.

4: Top 1/5 but not top 1/10 of submissions.

5: Top 1/10 of submissions.

but that doesn't mean that reviewers shouldn't be using factors such as Longevity and Novelty, and even Writing, in deciding their overall score. So, as you're all finishing your submissions, now is your chance to make a suggestion -- how do you think the PC should weight these various factors?

STOC -- Choosing A Program Committee

It took longer than I expected to put together a PC for STOC, and now that it's over, I thought I'd talk about the process.

First, I downloaded the PCs for FOCS/STOC/SODA for the last three years. I wanted to get an idea of what past PCs have looked like, and I wanted the raw data. Generally, I tried to avoid asking people who have served on those committees twice in the past three years. In my mind, it's good to mix things up and get new people involved in the process.

Then I tried to wrap my head around issues of coverage. I know authors are (reasonably) annoyed when they see nobody on the PC in their BROAD AREA X, leaving them wondering if their paper will get a fair read. Despite (indeed, because of) my readily apparent algorithms bias, I wanted to make sure there were a suitable number of people in complexity/cryptography/quantum etc. Even on the algorithms side, I wanted to make sure major areas like data structures, on-line algorithms, approximation algorithms, etc. were reasonably covered as well. It's hard to cover everything, so I'm sure some people will still be disappointed, but I think that overall there is a nice balance in the committee. (We'll see if it's a suitable balance once the papers come in...)

Besides covering areas, there were other balancing issues that came to mind. The "ages" of the PC members was perhaps the next most important. I wanted some fresh faces, since serving on a PC is both good experience for younger members of our community, and a signal to their departments (or bosses, or future bosses) that they are well thought of. But I also wanted some more experienced hands who could possibly head off my mistakes before I made them and provide appropriate judgment where needed.

Additional balances I tried to make: "Practical" people and "pure" theoreticians. Research lab/industry people and academics. (No, that's not the same as the practical/theoretical balance.) US and non-US participants. I did also consider the number of women on the committee. My practice in this situation was not any sort of direct affirmative action, but just to make a conscious effort to make sure that I wasn't overlooking the numerous well-qualified possible female PC members when sending out invites. I look forward to the day when I don't think it's necessary for me (and others) to make this effort, but I personally don't think our field is there yet. For those who are interested in such matters, the STOC 2009 PC is 25% female. In checking back over the PC lists for the last three years, this seems to be more than average for FOCS/STOC/SODA. I admit to being somewhat surprised (and disappointed) by that, and I leave it to commenters to discuss the importance of this issue to our community.

The biggest difficulty I found in getting the PC finalized was getting senior people to sign on. Roughly speaking, the probability of your willingness to serve on a PC seems to decline monotonically with years of experience (with perhaps a significant step-function drop post-tenure). In this case, I don't mean this as a criticism. I know that the people who declined are indeed quite busy with many other things, including larger-scale efforts to benefit and promote the theory community. Or, as one colleague put it to me when I explained the problem I was having, "Duh!" Anyhow, it took a couple of rounds of trials to find, in particular, more senior colleagues, and I thank them especially for their willingness to volunteer, and/or for just giving in to my begging.

[Come to think of it, my own PCing has declined post-tenure, though I'm still averaging at least a couple of larger conferences per year...]

Anyhow, at some point or another, an official call for papers will go up, but I think it's OK to announce the PC (subject to last-minute issues or changes):

Susanne Albers
Andris Ambainis
Nikhil Bansal
Paul Beame
Andrej Bogdanov
Ran Canetti
David Eppstein
Dmitry Gavinsky
Leslie Goldberg
Shafi Goldwasser
Nicole Immorlica
Anna Karlin
Jonathan Katz
Jonathan Kelner
Subhash Khot
Ravi Kumar
Michael Mitzenmacher
Kamesh Munagala
Rasmus Pagh
Anup Rao
Rocco Servedio
Mikkel Thorup
Chris Umans
Lisa Zhang

STOC 2009 : "Impending Doom"

Another surprise announcement: I was asked to be the PC chair for STOC 2009, and I accepted.

I have to admit, I was surprised to be asked, as I am, after all, somewhat vocal in my opinions, which are not always popular. (I was going to label myself a crank, with examples, here, here, here, and here, before someone else did, but I prefer "vocal".) Once asked, I found it hard to decline, despite the warnings that the job is a lot of work (and arguably little reward). It is an honor to be asked, I do believe in service for the community, and, most importantly, I felt it might lead to interesting fodder for the blog. (Obviously nothing confidential will be discussed, but the challenges of the process -- an inside view -- might be interesting.) It was something I was hopefully going to do once in my life. And (as Cynthia Dwork nicely pointed out to me, when I asked her about the job), I'm only getting older, and will have less energy.

Some people might be worried, given my noted worldview, that I might set out to change things drastically. I was thinking it would make a great joke to take "competitive analysis" off the list of topics of the call for papers, only to find it wasn't actually there. Rest assured that things will probably change incrementally; I respect the traditions, and I view the main part of this job to be selecting and empowering a solid, talented PC to do their best job.

The one change I'd really like to implement, so much so that I have to let people object already, is to introduce the rating system that conferences like SIGCOMM use:

5: top 5%
4: top 10%, not top 5%
3: top 25%, not top 10%
2: top 50%, not top 25
1: bottom 50%

I like this approach much better than trying to guess what everyone thinks a 7 means, or differentiating between a 6.3 and a 6.6. (Though, depending on the projected acceptance ratio, I could see changing the numbers a bit -- to top 10%, 10-20%, 20-33%.) I think this approach makes it easier to concentrate attention on controversial papers that need attention.

ICALP A list of papers up

The list of papers for ICALP (Track A) is now up.

This was a hard PC to be on -- lots of papers, and in fact lots of good papers, made it especially hard to draw the somewhat arbitrary dividing line. Congratulations to those who had papers accepted, and for the many that didn't, be aware that the decisions were very, very difficult to make.

Anti-PC Travel

Over at the new Computational Geometry Discussion Forum, they are discussing program committees, and Ileana Streinu argues that every PC should have a face to face meeting for final decisions. I couldn't disagree more.

Academic life involves a significant amount of necessary travel -- conferences, talks, NSF meetings, research collaborations. Requiring travel for a PC should be avoided, especially these days when any air travel is an unpleasant hassle, and electronic PC tools (like easychair) are becoming reasonably good. My other main objections:

1. Travel wastes PC members' time. For people with families, the cost is particularly severe, as overnight travel specifically takes away from family time.
2. PC travel costs. It either increases the cost of the conference, or PC members have to pay with their own grant money.
3. Extra air travel is ostensibly bad for the environment. Be aware of your carbon footprint!

What are the supposed benefits of face-to-face PC meetings, and how to respond to them?

1. It leads to better decisions. This seems to be a matter of faith with some people, but I have seen no real evidence for it. In my experience, online discussions can be as good as face-to-face discussions. In both cases, there are various types of noise, and decisions will not be perfect, but hopefully nearly so.
2. It saves time, by gathering people all in the same room to make decisions. Given the time required for actual travel, I doubt this is true. Even granting this, it isn't worth the loss in time flexibility. Getting on a plane means missing class, family dinners, etc.
   
3. It leads to better feedback. I do not see how this can be possible. Electronic PC meetings allow recording of comments and discussions, which should make it easier to provide better feedback, in the form of appropriate cuts and pastes, in the reviews to the authors.
4. It provides an opportunity for colleagues to get together. This I can't deny. Face-to-face PC meetings are usually more fun and informative than electronic ones. Does that really make up for the time/cost/annoyance of travel?

So in general, if a face-to-face PC meeting is required, I'll likely be saying no, unless I have some ulterior motive that makes the travel worthwhile.