The National Science Foundation (NSF) has a program called "Theory of Computing" which is the only program devoted to funding research in theoretical computer science. We use here "Theoretical Computer Science" in a broad sense, which includes research in Algorithms, Computational Complexity, Cryptography, Computational Learning, Network algorithms, etc. (Of course theoreticians can and do also apply to more application-oriented programs such as cybertrust and others)
Although the ToC program never had a large budget, looking at the projects and people it funded throughout its history, we can safely say that it had a huge impact much beyond the boundaries of TCS and even beyond the boundaries of Computer Science at large. Indeed, much of the initial research on field-transforming concepts like Quantum Computing, Boosting of learning algorithms, Cryptographic Protocols, Interactive Proofs, and more was supported by this program.
Unfortunately, the budget of ToC program has been more or less stagnant at approximately $7M per year since 1989 (in dollars without adjusting for inflation the ToC budget was $6.4M in 1989, $5.1M in 2004, and will be $7.2M in 2005). Needless to say, in these 15 years the costs of research (such as faculty salaries, student stipends etc.) grew even beyond the global rate of inflation. Also the overall CS budget at NSF tripled during this time. Thus the ToC program budget that was merely insufficient in 1990 and dangerously insufficient in 1999 is now at what can only be described as a crisis level. This is a situation that must be corrected if we wish our field to continue to thrive. Given TCS's achievements in the last few decades and challenges for the future, this should concern not only theoretical computer scientists.
What can we, TCS faculty in the U.S., do to fix this?
- First of all, educate ourselves about the funding situation and ways to solve it. If you can, please come to the business meeting at the upcoming STOC, where these issues will be discussed.
- We need to participate more in the NSF, this includes reviewing proposals, participating in panels, and volunteering for positions. NSF administrators are actually quite appreciative and supportive of theory, but the situation will not change without active community involvement. In particular, please consider volunteering for the position of director of the ToC program.
- We need to educate others about what we do. This includes bright math-inclined high school kids who could potentially become TCS researchers, educated adults (including also other scientists), and also other computer scientists. We need more popular science books, general audience lectures, essays and op-eds.
Here's a wacko idea:
ReplyDeleteHow about changing the name of the field?
Theory of Computing makes it sound like there are no immediate applications to what we do, whereas a lot of the work we "theoreticians" do can and does have immediate applications (e.g. indexing algorithms, network algorithms, crypto, and so on and so forth).
Very interesting post. I was not aware that there was a problem with TCS funding. It seems like CS departments keep growing all the time.
ReplyDeleteRegarding the first commenter:
ReplyDeleteI realize you were joking, but it's important to understand that the lack of funding is not because we don't have immediate applications.
For example, through one of the Link's in Lances post a few days ago, I saw DARPA's definition of basic science: "systematic study directed toward greater knowledge or understanding of the fundamental aspects of phenomena and of observable facts without specific applications in mind."
Not just our economy but our whole way of life is a product of people who pursued knowledge without immediate applications in mind, and funding such pursuit is the reason that NSF exists.
Moreover, people in Washington do understand that, and the theory funding problem is not because they think only applied research should be funded. It's more because we theoreticians were in general uninvolved in the funding process and allowed ourselves to be forgotten.
-- Boaz
I agree with Boaz. In this day and age, a good resume and a good grant proposal are not enough to get funded. You have to be involved in the funding process, as unpleasant and seedy as it is.
ReplyDeleteIndeed, the TCS community might be well served by hiring a lobbyist.
I hear Jeff Vitter's brother is a congressman. Maybe you can turn to him for some advice...
We can also learn something from AMS in this regard. See
ReplyDeletehttp://www.ams.org/government/congressfellowaward.html
the TCS community might be well served by hiring a lobbyist.
ReplyDeleteIsn't ACM/USA supposed to play this role? Perhaps what is needed is more volunteers participating in that body.
Alternatively, to take a cure from Lance's top 10 theorems: how about creating a list of the top 25 contributions from theory to day to day practice of computing and publishing it in either CACM or the new Queue. The list would be something along the lines of:
-LP interior point methods
-PKC
-NP-completeness
plus one particularly useful example from each of:
-approximation schemes
-randomized algorithms
-network algorithms
-spectral analysis (a la page ranking)
-indexing
-matching algorithms
-network flows
-interactive proofs
-quantum computing
-....
Boo hoo hoo. Now you know what professors in the math department are feeling. Think we get *NSF* money? Nope. We slave away with a huge teaching overlaoad, do high quality research, and get hardly a dime from the NSF. Welcome to the real world. If you want to get paid like an engineering professor buck up and start consulting. Commie CS profs always trying to get govt funding....
ReplyDelete"Boo hoo hoo. Now you know what professors in the math department are feeling. Think we get *NSF* money? Nope. We slave away with a huge teaching overlaoad, do high quality research, and get hardly a dime from the NSF. Welcome to the real world. If you want to get paid like an engineering professor buck up and start consulting. Commie CS profs always trying to get govt funding...."
ReplyDeleteYes, people in math departments DO get NSF funding. For example, NSF Math Science postdocs are given almost exclusively to pure/applied math postdocs and very few to TCS postdocs. Also, you are neglecting one of the main issues: Since it is well known that math departments have less money and that math is essential to university programs, there are many well established math postdoc programs in many universities, for example. In many top universities, a math professor can still have students even though they may bring in minimal funding. This is not possible in CS right now. Perhaps because TCS people have traditionally expected to get more govt funding--and because people expect them to get money since they are under the lucrative "CS" label--there are much fewer well established ways of dealing with this funding shortage, whereas math departments are much better adjusted to the situation. Perhaps this is one of the points here: if we can't get more funding, then we have to figure out how math departments deal with minimal govt funding.
Just to clarify, I don't think we (or anyone) deserve government funding.
ReplyDeleteThe issue is that the mission of theoretical computer science is very important and should be funded at a better level.
Although I am far from an expert on funding matters, I am sure that there are also other fields that are not funded as well as they should. The fact we're advocating for more TCS funding doesn't mean we don't support also increasing funding for these fields.
The last comment was by me. --Boaz
ReplyDeleteI do agree that NSF funds more of applied research. My M.S. thesis advisor was and still is involved in TCS. I was his only student who applied the work to real world problems and implemented it too. This helped him in obtaining the NSF career award and another grant too. Currently, he focuses 70% of his time on TCS and the remaining 30% on how it can be practically applied.
ReplyDeleteThere is an overall problem of funding in computer science (see the congressional hearings), not to mention mathematics, but the situation in theory of computing is really exceptional.
ReplyDeleteAdjusted for inflation, the 1989 budget for the theory of computing program (approximately $10M in 2005 dollars, see http://www.bls.gov/home.htm for an inflation calculator) was about TWICE what it was in 2004, and about one and half as much as the 2005 projection. Needless to say, tuition and other expenses have grown faster than inflation.
And this has not happened because NSF has taken the position that they are not interested in theory. Quite the opposite! The 2003 budget request sent by NSF to Congress mentioned the Spielman-Tang results on smoothed analysis as one of the three major results funded by NSF in all of computer science in previous years. The Guruswami-Sudan results are still featured on the NSF website http://nsf.gov/discoveries/disc_summ.jsp?cntn_id=100256&org=NSF as a major discovery (among all of science).
In any case, this is an extremely successful time for our field (think that just in the last few months, and just staying within complexity, there has been a proof that L=SL, a new proof of the PCP Theorem, and the resolution of the more than 10 years old question about embeddings of L1 in L_2^2) so it is an easy argument to make that this growth should not be chocked by lack of funding.
Luca
The NSF posting that Luca mentions in his comment contains an error of omission that, in my opinion, is unconscionable.
ReplyDeleteThe breakthrough work of Madhu Sudan was performed when he was an employee of the IBM T.J. Watson Research Center. The article by David Hart (on the NSF website) goes out of its way to include phrases like "his then-doctoral student...", and "now at the University of Washington" to be accurate about affiliations, but hides the fact that Madhu Sudan was with IBM at the time of the first, and arguably the bigger, step in the final result.
This kind of half truth in reporting from the most significant government organization devoted to supporting basic science is plainly disgusting.
Another ridiculous aspect of this article is that while it raves so much about the factor-of-1000 speedup achieved by Koetter and Vardy, it completely misses the point about what Sudan and Guruswami--Sudan achieve. There is no mention of the amazing mathematical significance, as exemplified by the consequences, of Sudan's breakthrough. It also misses a glorious opportunity to point out how huge breakthroughs are culminations of years of research from various threads, how Sudan's work had its more immediate motivations in PCP constructions, a matter of purely mathematical curiosity, and how it took advantage of algorithms for polynomial factorization, developed in the early 1980's in quite a different context.
--D. Sivakumar
(I work for IBM, but that's not why I wrote this comment.)
Please check whether the authors acknowledged IBM in their paper.
ReplyDeleteEven if there exists an employment relationship, does it mean that anything the employee does is necessarily at least partially supported by the employer?
I didn't check. So Einstein's papers should acknowledge the Swiss Patent office?
X
ReplyDeletePlease check whether the authors acknowledged IBM in their paper.
The author does of course mention his affiliation properly.
Even if there exists an employment relationship, does it mean that anything the employee does is necessarily at least partially supported by the employer?
I don't claim to be wise enough to answer this question.
I didn't check. So Einstein's papers should acknowledge the Swiss Patent office?
Again, my comment was not about the paper. It was simply that via the Hart article, NSF appears to claim more credit than it deserves. If some curious members of the congress look up the articles and find no mention of "NSF support", I am guessing that they aren't going to be thrilled.
D.S.
Factcheck:
ReplyDeleteIn the PDF version of the paper on IEEE Transactions on Information Theory website, there's no mentioning of either the word NSF or the word IBM.
I respect authors' decisions.
X
X, the paper that started it all is
ReplyDeleteMadhu Sudan
Decoding of Reed Solomon Codes beyond the Error-Correction Bound
Journal of Complexity Volume 13, Issue 1 , March 1997, Pages 180-193
That appeared with Madhu's IBM affiliation.
Please respect our decisions and go stand in the corner while we go back to discuss Boaz's post.
My apologies for not checking things thoroughly.
ReplyDeleteX