News from yesterday's Business Meeting (continued). Most of the news from NSF is a repeat of last years sorry state of affairs: no money, not enough influence.
Influence: We (TCS) are a lowly leaf, instead of a child of the root in the CS organizational tree. This is both bad for money, and very bad for influence and image. Bill Steiger is working hard for a change.
Money: bad news. More precisely, when Bill Steiger got to NSF, all his budget was already spent. (Budget = $4.1 million, plus 2.8, a share of the money for three subprograms). Of the ~500 CS proposals to NSF, about 90-100 were for Theory. Bill managed to fund 18, by hard work, persuading others to let Theory have a bit of their budget, etc. The SING (network) program was also seriously underfunded (~100 proposals, 7 funded, one of these was theory-flavored.)
Perspectives for 2007 are not good. Again, the money is pretty much spent, but Steiger will do the best he can. NSF budget should be within 10% of 2006. About 4-5 CAREER grants might be funded, no large Theory projects will be. SING will again be very competitive.
If you are interested in submitting a proposal do talk to Bill Steiger. He will try to help.
An appeal by Bill Steiger: please send "nuggets" to him—descriptions of neat Theory results. They are VERY useful.
Dick Karp spoke, and thanked Bill in the name of the Theory community. After a round of applause, Karp explained that other science communities lobby for NSF projects: astronomers get observatories, satellites; physicists get accelerators, or focused projects. They have an internal discussion and then lobby lawmakers and NSF. CS, in particular Theory, should do likewise.
He appealed for mobilizing the community. NSF wants CS to suggest visionary activities, and CRA got a few millions to organize us to suggest ideas. Theory should make sure we are well represented.
Avi briefly noted that out of 0.5 billion to CS, Theory gets 6-10 million, yet we are about 20% of the community. We need politics. We should also think of service at NSF as part of our service.
At the end of the meeting, it was announced that Hal Gabow will be the next TC chair.
The final part of the proceedings was moving to the adjacent ballroom where we were treated to a rock concert. Christos Papadimitriou, suitably dressed in all black was the keyboard player, Anna Karlin had one of the electric guitars: the rest of the band (Lady X and The Positive Eigenvalues) was unknown to me. Lady X was Andrea Frome (a Berkeley grad student), and the performances were very good. Eventually Christos also sang. (Luca reviews the concert with pictures.)
MONDAY talks.
There was an invited talk by Terry Senjowski, a distinguished neuroscientist. He talked about how vision is influenced by knowledge and expectations, and how our brains seem to have learning feedback mechanisms, and that simple neural networks can learn surprisingly complicated stuff. I can report more fully if there is interest; he did not make direct connections to Theory.
Again today there were a number of very interesting papers. A cute question from the point location talk: in 2D is nearest neighbor as hard as point location? As usual, clever crypto papers, and quantum results, including one by Xiaoming Sun and Andy Yao with real heavy duty math.
A most interesting/controversial talk was by Leslie Valiant. He explored paths to try to prove that NC2=P#P—he thinks this would be cleaner than the current complexity zoo. The paper is a continuation of the research direction started with his matchgate computations. He considers "holographic reductions" that conserve number of solutions, not by direct translation as the usual parsimonious reductions do, but in complicated ways: they are many-to-many maps but still conserve counts. Using these, he is able to prove interesting stuff, like counting number of satisfying assignments mod 7 is in P, but 7 may be the only such modulus.
The paper that won the Machtey award is very nice, and Nick Harvey did a superb job of presenting it. He has probabilistic algorithms to find matchings in non-bipartite graphs that achieve time O(nω) where ω is the exponent of matrix multiplication. There was another algorithm with the same bound (Mucha and Sankowski, FOCS 2004), but Nick Harvey managed to do what no other general matching algorithm does: it is easy to understand. Read it!
Finally a paper I could not hear, but is interesting if only to show how taste changes. Back in the remote prehistory of CS—around the very early sixties—people were very interested in small universal machines. They wanted to see how simple could objects be and yet have undecidability "built in." More precisely, for what pairs (s,a) is there a universal Turing machine with s states and a tape symbols? (The product sa is the "size" of the machine). The smallest machines were constructed by Minsky, using as a subroutine "tag systems" that are a kind of "Post production systems" that are a kind of type 0 grammar. The simulations introduced an exponential overhead, so these smallest machines were very slow. It has been an open problem for over 40 years whether this exponential slowdown was really necessary. The paper by Woods and Neary shows that this is NOT necessary, and gives a polytime algorithm for all known minimal-size universal Turing machines.
Bill Steiger is working hard for a change.
ReplyDeleteI found this comment quite hilarious. It sounds as though Bill Steiger usually does not work hard, and is doing so for a change :-)
Got a link to the #SAT%7 paper? That would be a great pre-processor...
ReplyDeleteWhat is the basis of this 20% number? It may hold true for some concrete universities, but it's very unlikely to be true worldwide.
ReplyDeleteAs Luca T said in his posting, FOCS only has 220 attendees, while is also unlikely to be 20% of anything. E.g., the most important data mining conference, KDD, has 600+ attendees, and many less theoretical conferences have even more participants.
Anon, 3:19pm: I am just guessing, but I think 20% comes from this sentence:
ReplyDelete"Of the ~500 CS proposals to NSF, about 90-100 were for Theory."
In any case, Theory's % in the general CS academic community is significantly bigger than 1%-2% of NSF funding that it gets. (It might not be 20%, but it's significantly more than 1-2%.)
Andris
Take the number of faculty members at top-10 research universities in the US, and see how many of these are theoreticians. I haven't done the calculation but I have been told that the result is between 10% and 20%. (Berkeley in on the low end, at about 15%.) Then take the number of new hires in the last five years at those universities, see how many of them were theoreticians, and the numbers are in the same range. NSF considers peer review as the main tool to assess quality, and the peer review system made of the collective computer science faculty of the top American universities (who make the hiring decisions) treats theory quite well.
ReplyDeleteDid you mean: terry sejnowski
ReplyDeleteAre we to assume that "top ten" makes up our community? Some sense of community, that.
ReplyDeleteDepartments below a certain "threshold" do not make much of a priority to hire theorists. The threshold is not "top 10" but it is real. Maybe top 30 or just "tier 1".
ReplyDeleteJust to second the comments of anonymous 8, the fraction of theory faculty once you get below the top 10 departments drops dramatically (as does the general departmental support for theory research).
ReplyDeleteI just want to check that when you reported
ReplyDeleteon Valiant's paper you weren't making a typo:
1) Does he REALLY thing NC^2 = P^{#P} ???
2) Is determining if #SAT \equiv 0 mod 7
REALLY in P ???
Please verify and link.
bill gasarch
The result about #SAT mod 7 is claimed in reference [17] here.
ReplyDeleteHowever, the result does not seem to say that #SAT mod 7 is in P, but something more restrictive.
Isn't funding also skewed highly towards the tier 1 universities?
ReplyDeleteValiant's #SAT mod 7 result is for formulas of the following restricted type: Start with a 3-regular planar graph (e.g. triangulate an arbitrary planar graph and takes its dual) and create a variable for each edge. Now create a clause for each node defined on the 3 edge variables that touch it.
ReplyDeleteValiant's claim was not that NC^2 should equal P^#P but that at the moment we have little reason to rule out the possibility that the two are equal since we can't rule out that we can solve #P complete problems using linear algebra. The mod 7 result in part illustrates how 'accidents' of linear algebra allow us to compute some very surprising things - our intuitions may be far from the truth. Valiant did give the value judgement that such a circumstance (e.g. NC^2=P^#P) might be preferable to a 'nightmare' of a vast complexity zoo of incomparable classes that don't really allow us to classify much of anything cleanly.
(cough cough)
ReplyDeleteVV isolation lemma
(cough cough)
@number 9, so you are saying once we reach to departments which are constrained, they consider theory lower priority? NSF is also funding constraint so the same reason for NSF to consider theory a lower priority must be justifiable.
ReplyDeleteFurther, it is not the number of faculty which is the right parameter to measure the ratio. The right parameter is the number of (grad) students. If there are fewer grad-students then theory faculty does not deserve more per capita for being inefficient. As far as I know, a major portion of faculty expense (9 months salary) comes from the departmental budget. Most of the NSF funding in theory goes to support grad-students (note that department share is proportional to the overall funding, so even this can be charged dollar for dollar to grad-students).
Could somebody throw an estimate on the proportion of grad students? Is it true that theory grad-students have less funding for traveling and RA ship etc?
Could somebody, let us say at Berkeley, confirm what fraction of grad-students have to do TA ship in theory vs non-theory?
There is no formula according to which NSF *ought* to distribute its budget.
ReplyDeleteNSF's mission is to promote scientific research, and not to equally distribute grants accross all faculty.
The question is whether spending more than 1-2% on theory will advance scientific research.
The decisions by top-10 departments seem to be an indication that they believe theory is a more significant part of CS than 1-2%, but it's of course only an indirect indication.
The original post had stated that Bill Steiger had cut budgets of existing grants. In fact no existing grants had their budgets cut. I updated the post.
ReplyDelete