Thursday, May 15, 2008

The Week Ahead

Neither Bill or I will be attending the upcoming STOC in Victoria. Have no fear, we have once again enlisted an excellent guest poster to keep you all abreast of the latest happenings.

On Saturday in Seattle, there will be a Visioning Workshop with two goals.

  1. Identify broad research themes within theoretical computer science that have potential for a major impact in the future, and
  2. Distill these research directions into compelling "nuggets" that can quickly convey their importance to a layperson.
We have workshops like this every now and then (remember Portland?), and it is good for our community to occasionally step back and make the case for theory, both to attract good researchers and funding, but also to ourselves so we don't lose sight of the basic reasons of why we do what we do.

At the STOC business meeting, Borodin will discuss his co-authored letter about conceptual contributions that has already appeared on Scott's blog. Nobody seriously argues against papers with important conceptual points, rather we have the problem that STOC and FOCS have gotten to the point that they accept only a fraction of the strong papers in a given year and difficult decisions have to be made and it is much easier to recongize a strong technical paper than a strong conceptual one. Still both the STOC and FOCS 2008 committees are fighting back with the new line added to the call.

Papers that broaden the reach of theory, or raise important problems that can benefit from theoretical investigation and analysis, are encouraged.
We can only recognize true conceptual greatness when it stands the test of time conflicting with computer science's deadline-driven conference system. Something has to give.


  1. Oh Lance, I could but anticipate your ending this seemingly innocuous post with some bait :).

  2. the test of time conflicting with computer science's deadline-driven conference system

    This sounds like one of those Jeopardy "Before and After" lines with pivots on "time" and "conflict".

  3. I think everyone is willing to concede that many (if not the majority) of STOC/FOCS papers do not stand the test of time. On the other side of the coin, how many great papers (results that have stood the test of time) have been submitted and rejected from STOC/FOCS? The difficulty of knowing the rejected papers aside, I'd wager that its very very few.

  4. This comment has been removed by the author.

  5. Anonymous #3: I think the number of rejected papers is larger than you'd suppose, but I'll leave it to others to argue. (I certainly have had conceptual papers rejected from SODA, for instance.)

    Then there's also the aspect that some conceptual papers never get submitted to FOCS/STOC because authors are self-selecting. I'll throw out an example: our paper on "The Hiring Problem and Lake Wobegon Strategies" was well-received at SODA, and I think had some interesting conceptual ideas. Obviously, the test of time does not apply; who knows how history will judge the paper. But I would have resisted sending it to FOCS/STOC, because I would have predicted it would have been rejected for not being, well, FOCS/STOCy (technical) enough.

    I'd imagine that many others are self-selecting the same way.

  6. While we are harping about conference accepts, I have always wondered why the list of accepted papers does not include abstracts too.

    I doubt it will violate IP rights of the publishers; for instance abstracts of STOC are available on ACM website for free.

    It would take some extra work on the behalf of the PC chair, but no more than 5 minutes if done cleverly: our submissions do include a textbox for the abstract.