James Lee posts a note from the Visioning workshop held ahead of STOC 2008. There's some interesting news about the restructuring of CCF (the "theory" section within the NSF's Computer Science directorate). The previous CCF structure (run by Michael Foster) consisted of:
- Theoretical Foundations (TF), which included all of theoryCS, as well as geometric modelling, some visualization, information theory, and signal processing.
- Foundations of Computing processes and artifacts, which among other things included graphics and visualization, as well as some software, architecture, and programming languages
- Emerging models, which had quantum, nano, and DNA computing.
- Algorithmic Foundations
- Communication and Information Foundations
- Hardware and Software Foundations
One interesting comment was that geometry will be folded back into the main cluster. Currently, CG, geometric modelling, and symbolic methods have a separate pool that awards are made through, under the larger TF cluster. It sounds like this will change, and CG will "compete" in the main theory pool.
This will probably make life interesting in the short run. I don't think I'm overstating the case to say here that there's a not trivial amount of hostility between CGers on one hand, and the "regular" STOC/FOCS crowd on the other. If I had a dollar for each time someone vowed never to attend STOC/FOCS because of perceived slights to geometry, I'd never have to write grant proposals. On the other hand, I have heard (from various sources) of people who say things like 'Geometry is not real theory'.
It should be interesting to see how this all shakes out during panel review. I suspect/hope that things will happen reasonably, in that proposals will be binned and panelists assigned appropriately.
I'm not a CGer, and it's unclear to me just how much commerce of ideas happens between CG and 'mainstraim' CS theory. But I do know it's a nonzero amount, and I expect CG could improve its standing in the new organizational setting by publicizing this and expanding research in the intersection of the two areas.
ReplyDeleteOff-the-cuff examples, both from lower-bounds work:
-emphasize that geometric data structure problems have interesting, successful lower bounds within the (shared) framework of communication complexity. Many problems are hard because they express the set disjointness problem (Mihai has a very interesting new paper extending our understanding of this), and this connects them to the Theory 'canon' and makes them seem approachable by outsiders.
-3SUM-hard problems are an intriguing phenomenon, which however seems to be unknown to many/most Complexity people (I learned about it from this blog). This and any other classes emerging from geometry should be publicized further; what would really make people take notice is if one could give some kind of logical or circuit characterization.
None of this is to say that the most important parts of CG are the ones which look most like standard complexity theory or algorithms; but, again, these parts are probably useful in building recognition and standing in the new regime.
Which paper of Mihai are you referring to ? I'm intrigued.
ReplyDeleteSuresh: Check out "(Data) STRUCTURES" on Mihai's list of papers.
ReplyDeleteSo out of curiosity, does CGers hostility toward FOCS/STOC also extend to SODA?
ReplyDeletenope. Sausage and soda go well together.
ReplyDeleteyes, "(Data) STRUCTURES".
ReplyDelete