Loading ...
Sorry, an error occurred while loading the content.

[Computational Complexity] Growth Causes Shrinking

Expand Messages
  • Lance
    Jeff Erickson makes an important point in his post on the SoCG (Computational Geometry) business meeting. Links and emphasis are his. Finally, and most
    Message 1 of 1 , Jun 8, 2005
      Jeff Erickson makes an important point in his post on the SoCG (Computational Geometry) business meeting. Links and emphasis are his.
      Finally, and most importantly, there was no discussion of the theory community's efforts to increase NSF funding for theoretical computer science, as there was at the (also beer-free) STOC business meeting. One question in particular was never asked: Are we computational geometers still even part of the theory community? The answer should be a resounding NO!, followed by a slap to the back of the head—of course computational geometry is part of theory! Look, we have big-Oh notation! Unfortunately, reality seems to disagree. None of the new material on TheoryMatters mentions computational geometry at all, although it does mention another border community: machine learning. With few exceptions, the computational geometry community rarely submits results to STOC and FOCS; this was not true ten years ago. Lots of geometric algorithms are published at STOC/FOCS by people outside the SOCG community, but nobody calls them computational geometry. (Sanjeev Arora's TSP approximation algorithms are the most glaring example.) For many years, computational geometry has been funded by a different NSF program than the rest of theoretical computer science. (This worked to our advantage when graphics was getting lots of money, but that advantage is now gone.) At one infamous SODA program committee meeting a few years ago, one PC member remarked that nobody at SODA was interested in computational geometry, they have their own conference, they should just send their results there. (This declaration led another PC member to resign.) Apparently, the divorce has been a complete success.
      Not just computational geometry, but the COLT (Computational Learning Theory) and the LICS (Logic in Computer Science) communities used to have their best papers in STOC/FOCS but now we see few of their papers in the standard theory conferences. As the theory community grew larger and broader, the STOC and FOCS conferences started to emphasize certain areas in theory. Those areas which were not greatly represented felt some resentment and started putting more and more emphasis on their own specialty conferences, in some cases eventually abandoning STOC and FOCS altogether.

      The Conference on Computational Complexity started in 1986 as the Structure in Complexity Theory Conference (Structures) by some researchers who felt their interests of complexity were not being well represented in STOC and FOCS. This view becomes self-fulfilling—sometimes very good papers would be turned down from STOC and FOCS because they were considered a "better fit" for Structures. In response we changed the name in 1996 and brought a broader view in complexity to the conference (though not without some controversy) and tried to work our way back into the STOC/FOCS community.

      Other conferences like COLT, LICS and SoCG have moved the other direction. Note that SoCG also decided not to join the Federated Conference in 2007 while both STOC and Complexity will be there. I don't expect to see COLT or LICS at FCRC either.

      What can we do, if anything? STOC and FOCS cannot properly cover the broad range of areas that have ever been considered theory. Unless we have a major restructuring of how the general theory conferences operate, we will continue to shrink the vision of theory as the area continues to grow.

      Posted by Lance to Computational Complexity at 6/8/2005 06:13:00 PM

    Your message has been successfully submitted and would be delivered to recipients shortly.