Wednesday, February 09, 2011

STOC 2011 accepte papers posted.You heard it here...12th!

For those who did not read yesterdays comments or Lance's Tweet (the empty set?) the list of accepted STOC papers is here.
  1. 84 papers accepted. I personally think that there is enough high quality work that they should have more. However, I do not know what constraints the Program Committee had in terms of scheduling.
  2. Lance thinks we should give up this model of high-prestige conferences all together and grow up. I am less radical--- I think that conferences should have higher acceptance rates and have other activities for people to get information out there. Posters, satellite workshops, rump sessions, and half-day seminars are all good. FCRC will have some plenary talks which is also good (I am not sure if they will have any of the other items I mentioned.) At a math conference I went to they had a Math Jeopardy competition for undergrads. That was JAWESOME!!! (My ugrads tell me this is the new `Awesome and it means Jaw-dropping Awesome. They could be punking me.)
  3. Some people have said that there are less algorithms papers than usual or more complexity papers than usual (is that the same thing?). Is this a general trend for STOC and FOCS or is that just this one time?
  4. Is it true? I tried doing a count but it was hard to tell how to classify things. Some papers were in both, some in neither, some hard to classify, The whole endeavor reminded me for the W(4,5)th time how pointless some classifications can be.
  5. Is it important? If GREAT papers in algorithms do not get in because GOOD papers in complexity (or something else) do, that would be a problem. Other than that it is not a problem.
  6. Lance has suggested that we should have a conference where all the subdisicplines of CS get together and hold hands and sing Kumbaya. Is FCRC like that? Is it as close as we'll ever come? Are there too many different subfields of CS that don't care about each other to really have a conference like that?


  1. My impression is that good papers in complexity are being accepted and no good (only great--unless they have some AGT connection) papers in algorithms are accepted. So yes, that is a problem.

  2. This is amazing breaking news to share. Thank you.

  3. What counts as algorithms? There are plenty of papers that are not in "complexity theory" -- game theory, learning theory, privacy, cryptography, metric embeddings. The main results in many of these papers are algorithmic. Do they not count?

  4. Anon #3 : Just because a paper "has an algorithm" in it does not mean it's an algorithms paper. When I have an algorithm in a coding theory paper, I still call it a coding theory paper. (When a biology paper has a differential equation in it, that doesn't mean we should call it a math paper.)

    Having had this "discussion" before, I think an issue is that "algorithm" has just now become overloaded. I think when people say there aren't many "algorithms" paper, they mean there are comparatively fewer papers about algorithms that people actually use or may want to use in the near-ish future to solve an actual problem (as opposed to making a mathematical point). Of course, other people saying that may mean something different, and perhaps they'll chime in.


    Bill --

    I'm assuming you didn't mean to be denigrating with that Kumbaya comment, but it didn't sound so nice to me. I just got back from the still-going-on ITA workshop ( -- a very broad and big get together of information theorists (and others -- they seem to be inviting more computer scientists). They also do the big get together thing at the annual Int'l Symposium on Information Theory conference. These things tend to be 5 or so days, with various business meetings, awards ceremonies, special lectures for grad students (career training and such) entertainment, etc. scheduled to coincide. ISIT, last I checked, gets 700-800 attendees regularly.

    There are pros and cons to both conference approaches, certainly. I wouldn't try to deny that larger, more open conferences have the tradeoff that average paper quality is lower, and the hassle of figuring out which parallel session to go to can be frustrating. But I'm consistently surprised at the reluctance of the TCS community to seriously consider this as an option.

  5. MM- no insult intended--- I meant a conference that WELCOMES all branches of CS.

  6. There are also several papers on graphs/networks algorithms (I have no idea whether they will be used in the nearish future).

  7. BTW (perhaps I am showing my age) but 'jaw-some' comes from the horrible nineties cartoon 'Street Sharks'. They were sharks with legs. I was in middle school back then. It was their catch phrase.

  8. Well, seeing as you rushed to post a link to the STOC accepted papers even before the public list is available, but never commented on the list of papers accepted to SODA, this may be indicative of the "general trend".

  9. "Are there too many different subfields of CS that don't care about each other to really have a conference like that?"

    Is the Grace Hopper Conference about caring about each other as people (specifically as women in CS) rather than caring about actual disciplines?

  10. Though I wasn't part of this, I'll bet that 84 was actually a real limit.

    There are very signficant constraints on the # of papers in ANY 3-day 2-track conference assuming a minimum of 20 min talks with 5 min to move between talks in the middle of sessions. This can comfrotably be as many as 96 papers, 32 per day organized in four 95 min parallel sessions each having 4 papers. With a 30 min bathroom/coffee break you get 3:40 min total per half-day. This would be 8:50-12:30 and 2:00-5:40 for example. Any award/plenary talk of the same length subtracts 1 from the number of papers and also adds extra time to move between session formats.

    By making people uncomfortable one can add one extra pair of talks each day to get to 102 total (minus the number of award talks).

    At FCRC there is an hour in the late morning slated for FCRC-wide plenary talks. Each such talk would kill slightly less time than 6 talks for a total of almost 18 talks over 3 days which gets you 84 talks. The only way that they'll get award/plenary talks in is by slight juggling because the cost of each is "slightly" less than 6 talks.

  11. Michael M. defines an "algorithm" to be a positive result that might expected to be implemented. Surely we can find a better name for that than "algorithm". Maybe "practical algorithm" or "possibly practical algorithm".

    Warren S.

  12. Warren:

    I certainly didn't mean to suggest that I was defining algorithms -- just the opposite, I said that the term was overloaded with meanings.

    But if your interpretation of what I mean was that I thought some people lamented the apparent lack of possibly practical algorithms in FOCS/STOC, that sounds right!

  13. > Well, seeing as you rushed to
    > post a link to the STOC accepted
    > papers even before the public
    > list is available, but never
    > commented on the list of papers
    > accepted to SODA, this may be
    > indicative of the "general
    > trend".

    This is supposed to be a complexity blog, so they have no obligations to blog about conferences with a different focus. But Bill/Lance could have at least posted a list of lower bound papers in SODA (they can still do it).

  14. Michael,

    It is perhaps not apparent from the title & abstract which algorithms are possibly practical.

    Our paper "A General Framework for Graph Sparsification" gives a variant on the Benczur-Karger algorithm that is quite a bit simpler to implement. I was tempted to implement it myself, just for fun, but decided to wait until I have an undergrad looking for a term project.

    Another good paper to try to implement would be "High-rate codes with sublinear-time decoding". For this one, even the abstract hints that it might be practical. There could be many interesting applications if the algorithm were indeed practical.

    I think you've previously commented on "The Power of Simple Tabulation Hashing", but for the sake of others who haven't seen it, I'll point out that they even did an experimental evaluation.

  15. There is a related statement toJust because a paper "has an algorithm" in it does not mean it's an algorithms paper.

    Also, just because a paper "is not an algorithms paper" does not mean it's a complexity paper. Too often I see some sort of sniping in blog comments seeing these as two competing poles. To me, a noticeable feature of our field (and very evident in the STOC program) has been the growth of topics and papers that don't neatly fit in the spectrum between these two poles.

    Micha Sharir gave a plenary talk at SODA a few years back making the point that for computational geometry, at least, among the most important directions was the solution of underlying combinatorial and geometric questions, independent of any specific algorithm. This kind of thing has become increasingly true in other aspects of TCS.

  16. A great (unrelated) article by "Time" from 1982 on cryptography.,9171,953625-1,00.html