I feel a little déjà vu here. Ten years ago Karp led a NSF sponsored group with the mission of suggesting where the NSF theory group should focus its funding. The group held a panel discussion at the end of the 1995 STOC conference. Representatives from different subfields gave a short talk on the importance of their fields. After these presentations the panel opened the discussion to the audience.
Now instead of a physical panel discussion, Arora asks for a virtual one in a hope to draw from a larger base of people. Feel free to leave your ideas as comments on this post, on the committee page of the Theory Matters Wiki (edit password: tcs), or just by email to one of the committee members. Not everyone was happy with the last Karp report, so better to get your comments in now than complain afterwards.
I think you have a mistaken impression as to what this committee is about.
ReplyDeleteThis is not about setting directions for theoretical computer science (although some occasional self-reflection, as will go on in the course of this work, may help people gain insight into possible directions). This is an effort to build a case that theoretical computer science merits more funding than it is receiving from the relevant agencies, including NSF. Building such a case seems important as a step toward improving the dismal funding situation -- see that wiki for more on this topic.
As has become clear in talking with people from NSF, unfortunately theory cannot make an "entitlement argument". That is, we can't explain all the wonderful things we've done and ask for more money so that we can do more. I personally find this somewhat absurd, as I would think a proven track record might be useful in determining appropriate funding levels, but that appears to be the hand we're dealt.
So to make a case, we are left with describing what we will do in the future. This means extrapolating from where we are now to where we think we'll be 10 years from now. As part of this, we want to make sure that we include any new and exciting areas that may have a lot of impact, even if currently there is little work in the area.
Self-assembling nano-machines seems like such an area, as an example. (I just saw Ashish Goel give a talk on the area.) Right now it seems ambitious and far off; but as a challenge for a decade from now, it seems like a good topic -- theory can (and should) certainly have an impact.
This does not mean we leave out "core theory" for perhaps untested, new ideas. We should also extrapolate the exciting issues in core theory as well. Given the SL = L result, finding the ultimate limits of derandomization (RP = P?) would also be a large-scale goal.
BTW, I volunteered for the committee. As readers of this blog know, I have real trouble keeping my mouth shut (when I have an opinion). That seemed like sufficient qualification to me... but hopefully others will want to have input too.
Can you comment on the actual impact the 1995 committee had on NSF funding and the direction of the field? Did you or people you know actually change directions as a result of the report or the resulting funding priorities? I ask because I am trying to get a feel for how these reports translate into research directions.
ReplyDelete-David Molnar
I agree with all that Michael said. I have RSI problems so I will keep this brief. Influencing things in Washington takes time and effort. I think the TCS community is still figuring this process out (as Lance notes, this is version 3.0). I was too junior to be involved in the 1995 and 1999 discussions but I believe the community spent too much time trying to agree upon the research goals and perhaps not enough on the political process. Nevertheless, the earlier efforts did bear some results. In particular, the ITR program, especially in the first 2-3 years, was friendlier to TCS researchers than past NSF programs had been. NSF now appears to include some TCS people in the CISE advisory committee, so we have a better shot at having our concerns heard. (Many of the readers here may know that the CISE AC already discussed TCS funding for an hour in April's meeting, and that TCS budget got a modest raise.) TCS is respected more and more in CS.This spring five of the top 10 CS depts ---Stanford,
ReplyDeleteCMU, Cornell, UW, UIUC-- made offers to five different junior TCS people (and that is just the count for the STOC/FOCS community; I don't know about the rest of TCS.).
No need to be cynical at all!
Also, I encourage all people to consider applying for positions in NSF/CISE whenever they are advertised. Liason with NSF in this regard is another task for the committee.
p.s. The following email from Gabow (dated May 29) to all sigact members explains what this committee will do. It is more of a liason/lobbying body; composed essentially of volunteers. Gabow actually got very few volunteers. I guess he should have advertised on the blogs. :)
ReplyDeleteIn any case I am hoping that more people are able to volunteer a day or two to write up a nice 1-page description of a broad research direction.
Cheers, SA
------gabow's email-----
As a consequence of the long and interesting discussion of theory funding at STOC (powerpoint slides can be found at the SIGACT website; see http://theorymatters.org/ 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 chair.sigact@sigact.cs.unlv.edu
Actually, I thought I had volunteered for the committee but I don't recall ever even getting a response...
ReplyDeletewhat i meant to say was that everybody on the committee is a volunteer.
ReplyDeleteMy point was that it seems disingenuous to keep asking for volunteers when it is clear that you are only looking for certain kinds of volunteers (in particular, very senior people).
ReplyDeletePS: I don't have a problem with this fact, I just wish it was made clear in the initial email from Gabow.
The comments from Oded are quite valid. It is quite akward that we are asked to predict were exactly will TCS have an impact.
ReplyDeletePerhaps we need to explain this in terms the current administration understands: we make the high impact bombs, it is up to others to decide which country gets bombed.
This very much reflects what has happened in the field. Who could have predicted in 1987 that a field called bioinformatics would appear and be driven by algorithmic techniques? Who could have predicted in 1991 that the Internet would become so big that it would necessitate state-of-the-art algorithms for its day to day use?
Sure, if they want us to make predictions we will, but I think we should emphasize that a big part of the value of theory is that is ready to be applied wherever is needed. This applicability of TCS is derived from the generality and abstraction of its techniques.
--Who could have predicted in 1991 that the Internet would become so big that it would necessitate state-of-the-art algorithms for its day to day use?"
ReplyDeleteUm, that would be us.
Nope, sorry. In 1991 it was still very unclear if the internet would go anywhere outside the academic world. The release of the Mosaic and Netscape browsers in 1993/1994 were the factors that placed the Net into massive data territory.
After all, both areas require solutions to (then) unforseen computational problems on absolutely ENORMOUS bags of data,
That isn't enough. Numerical analysis also deals with massive data sets and so far the impact of classical (discrete) TCS techniques has been minimal there. Ditto for radio astronomy, or weather prediction or data mining, or lexical analysis or .... you get the picture.
Not every massive problem is solvable by clever data structures. Some massive problems are solved by understanding the underlying phenomena and using those properties to produce better programs (see e.g. computational finance).
In the case of computational geometry, such deep understanding happens to fall, more or less, within the purvue of TCS (although some discrete geometry papers are still controversial accepts as someone else pointed out), but in the case of, say, comp. finance they are squarely outside CS and well into economics and actuarial science.
Back to the point. Simply pointing out that the problem is big doesn't mean it's solution is contained in TCS.
Michael Mitzenmacher said:
ReplyDelete"As has become clear in talking with people from NSF, unfortunately theory cannot make an "entitlement argument". That is, we can't explain all the wonderful things we've done and ask for more money so that we can do more. I personally find this somewhat absurd, as I would think a proven track record might be useful in determining appropriate funding levels, but that appears to be the hand we're dealt."
Is that what the entitlement argument means ? I heard at least a few other (weaker) interpretations, e.g.,
"The fact that there are many of us does not mean we should get lots of funding"
"The fact that we got funding in the past does not mean we should get (comparable) funding in the future"
Etc. I'd appreciate comments on this.
Piotr
Anonymous said:
ReplyDelete"Numerical analysis also deals with massive data sets and so far the impact of classical (discrete) TCS techniques has been minimal there. Ditto for radio astronomy, or weather prediction or data mining, or lexical analysis or .... you get the picture."
The fact that TCS did not have much impact in some areas does not necessarily mean that TCS approches are not applicable there. Instead, it could simply mean that we missed an opportunity to apply them.
From this point of view, identifying promising areas early enough is of high importance, if we do not want to miss future opportunities.
And, I agree: proper data modelling (as opposed to assuming the worst case) is often crucial to solve a problem. Still, you often need fast non-trivial algorithms to deal with the resulting models. These two approaches (modelling and algorithm design) are often complementary, not disjoint.
Piotr