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):