Wednesday, June 29, 2005

New Theory Task Force

A growing concern in computer science, and in theoryCS, has been the dwindling of research funding and support from the government (NSF/DARPA/etc) at a time when interest in computer science among undergraduates is dwindling, and the US appears to be losing its edge in basic science.

Especially in theoryCS, there is a growing sense that we need to articulate a vision of the field that is more about CS as a way of thinking, than solely as a field that develops IT infrastructure. Lance had mentioned TheoryMatters earlier: it's a new clearing house for information on why theoretical computer science matters, and how the current funding crisis affects the work that we do.

In the next phase of this project, SIGACT (the theory arm of the ACM), has set up a committee that will deal with funding, outreach and advocacy issues. Here is the original missive from Sanjeev Arora:
SIGACT has set up a committee that will deal with funding, outreach, and advocacy issues. It will also explore and promote funding opportunities for TCS in NSF and other funding agencies. The members are: Richard Karp (chair), Christos Papadimitriou, Avi Wigderson, Richard Lipton, Bob Sloan, Madhu Sudan, Sanjeev Arora, Michael Mitzenmacher, and 3 ex officio members from the Sigact EC: Hal Gabow, Éva Tardos, Joan Feigenbaum.

One of the things we plan to work on is preparing a list of "research directions" for TCS in the next decade or two. Unlike a similar list from 2000 this one will be kept brief. It will have a few compelling items that will be comprehensible to nonspecialists and congressional aides. These will show that funding TCS is in the national interest.

We welcome your suggestions. Let's all put some thought into this. We should not be afraid to take on big challenges. Obviously, a brief list will not cover all of TCS but it is hoped that a long-term focus by funding agencies on some of the list items will benefit many or even most TCS researchers.

This is your time to speak up. If you have thoughts on this matter, (and if you are a theoretician, you should!), you may comment here, or even better, at the comments section of the TheoryMatters page (the password is the three first letters of "theoretical computer science", all in small case). Think big ! And don't be afraid to be speculative.

Here is my (first) contribution, on (what else!) computational geometry:
For the past many years now, biologists have been accumulating X-ray crystallographic structures of proteins, and developing a rich understanding of the crucial role that protein shape plays in determining its function. Today, the Protein Data Bank holds over 30,000 protein structures, and this number is constantly growing.

Understanding protein shapes, performing structural comparisons of molecules, and manipulating large molecular structures all require a sophisticated understanding of topology, geometry, and shape theory. In fact, one of the most active areas of research in geometry has been the area of "computational topology", which includes a large body of work on the use of topology in modelling shapes, especially proteins.

Being able to manipulate shapes efficiently is a core tool in doing the kinds of large scale structural biology that protein biologists have long dreamed about. Fundamentally, if I can classify the shape of a protein by comparison with others, I have learnt a lot about its function.

One goal of computational geometry should be to continue explorations in shape modelling and manipulation, with particular emphasis on the kinds of tools needed to compare and process large protein structures.

Update: There were some complaints about the make up of the committee. As Sanjeev Arora points out in the comments, Hal Gabow sent out a general invite to all SIGACT members, and not many people responded. It's important to note there are many ways to contribute to this effort.


  1. "The members are: Richard Karp (chair), Christos Papadimitriou, Avi Wigderson, Richard Lipton, Bob Sloan, Madhu Sudan, Sanjeev Arora, Michael Mitzenmacher, and 3 ex officio members from the Sigact EC: Hal Gabow, Éva Tardos, Joan Feigenbaum. "

    This list tells a lot why the TCS community is in trouble:

    - It's so so so expected...

    - There is a lot of overlap in research areas between members (and many of them are collaborators).

    - As a result of the over-representation of a very particular type of theory, several research areas that consider themselves part of TCS are not represented (or under-reperesented).
    Think security; think (more) algorithms; think computational geometry; think parallel; think distributed... and more.

    - All women are ex-officio. Why? It is not too difficult to come up with names that can replace almost any selected member, or that can be added without "diminishing" the stature of the committee.

    The real issue is not represtentation; what's at stake is the inputs provided by committee members,
    and the credibility of its output.

    Posted by Anonymous

  2. I do agree that there are many areas in TCS that are not "covered" by members of the commitee, especially geometry. Since I was not privy to the commitee formation process, I don't know how things were set up.

    It's a start: of course a lot will depend on how things work going forward, what kind of outreach there is, and what areas of interest get emphasized. More than this is hard to say at this point.  

    Posted by Suresh

  3. I am sure the committee is not averse to any one
    volunteering from the so called "ignored" areas.
    Chazelle wrote the op-ed with Arora and he is
    from geometry. I am pretty confident that the
    members on the committee can represent crypto -
    security encompasses much more than what TCS
    can claim to. It is easy to criticize from the
    outside - if you are in an area that is important,
    write to Arora, he is seeking input!!! 

    Posted by Anonymous

  4. In late May Hal Gabow sent email to all SIGACT members asking for volunteers for this committee. Total number of volunteers (he showed me the list): a dozen or so.
    Most were taken from this list.

    Unfortunately, my impression is that not too many people
    even want to do this kind of work. (The ex officio people are in because they wanted to be on the committee, not because they were appointed.)


    Posted by Sanjeev Arora

  5. Here's the letter that Hal sent out (thanks, Sanjeev). Emphasis is added:

    Subject: TCS Funding Committee
    From: Hal Gabow
    Date: Mon, 30 May 2005 20:37:42 -0600
    To: SIGACT Members

    As a consequence of the long and interesting discussion of theory funding at STOC (powerpoint slides can be found at the SIGACT website; see for additional information), the SIGACT Executive Committee is forming a standing committee that will actively pursue this and related issues. In addition to members who will be invited by the EC, this message solicits self-nominations to the committee . The approximate time commitment will be roughly the same as serving on the PC for STOC/FOCS, but distributed over the entire year.

    Some goals for this committee:

    (A) Act as liaison between funding agencies and the SIGACT community. In particular to offer advice and the visions of the TCS community to NSF.

    (B) Ensure that TCS viewpoints are represented within the broader discussion of funding for all of computer science.

    (C) Facilitate and coordinate the development of materials that educate the rest of the world about TCS.

    Please send responses to

    Posted by Suresh

  6. I've been thinking a little bit about the demise of computer science vis-a-vis funding and enrollment. Lance has said on his blog that coming up with good open problems in CS is pretty difficult. It would seem that since he hasn't ever listed any such open topics that perhaps there aren't really any interesting problems (i.e. except for P != NP) or the very few ones that do exist are hard to come up with. Note that other fields like math and molecular biology seem to have no end to the number of important open problems in each domain. So...if CS really can't come up with good open problems then why should CS receive a lot funding? If the field really has stagnated then shouldn't all those CS researchers move on to more lucrative fields like math? 

    Posted by Anonymous

  7. This is a terrible misunderstanding of Lance's post. His post was an answer to a grad student question. Obviously, the kind of open problem a grad student might work on is something that should bear fruit relatively quickly, i.e should not be significantly hard. It is those kinds of problems that are hard to find.

    There are innumerable open problems in all areas of computer science (both theoretical and otherwise). Trust me, we haven't even begun to understand the space of problems that are out there. 

    Posted by Suresh


Disqus for The Geomblog