tag:blogger.com,1999:blog-3722233.post111627224266952601..comments2024-03-18T23:13:09.570-05:00Comments on Computational Complexity: Crisis in Theory FundingLance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger18125tag:blogger.com,1999:blog-3722233.post-1116454477041362992005-05-18T17:14:00.000-05:002005-05-18T17:14:00.000-05:00My apologies for not checking things thoroughly.XMy apologies for not checking things thoroughly.<BR/><BR/>XAnonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1116446122644701082005-05-18T14:55:00.000-05:002005-05-18T14:55:00.000-05:00X, the paper that started it all isMadhu SudanDeco...X, the paper that started it all is<BR/><BR/>Madhu Sudan<BR/>Decoding of Reed Solomon Codes beyond the Error-Correction Bound<BR/>Journal of Complexity Volume 13, Issue 1 , March 1997, Pages 180-193<BR/><BR/>That appeared with Madhu's IBM affiliation.<BR/><BR/>Please respect our decisions and go stand in the corner while we go back to discuss Boaz's post.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1116433292395304762005-05-18T11:21:00.000-05:002005-05-18T11:21:00.000-05:00Factcheck:In the PDF version of the paper on IEEE ...Factcheck:<BR/><BR/>In 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.<BR/><BR/>I respect authors' decisions.<BR/><BR/>XAnonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1116428788214460792005-05-18T10:06:00.000-05:002005-05-18T10:06:00.000-05:00Please check whether the authors acknowledged IBM ...<I><BR/> Please check whether the authors acknowledged IBM in their paper.<BR/></I><BR/><BR/>The author does of course mention his affiliation properly.<BR/><BR/><I><BR/>Even if there exists an employment relationship, does it mean that anything the employee does is necessarily at least partially supported by the employer?<BR/></I><BR/><BR/>I don't claim to be wise enough to answer this question.<BR/><BR/><I><BR/>I didn't check. So Einstein's papers should acknowledge the Swiss Patent office?<BR/></I><BR/><BR/>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.<BR/><BR/>D.S.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1116395746643120302005-05-18T00:55:00.000-05:002005-05-18T00:55:00.000-05:00Please check whether the authors acknowledged IBM ...Please check whether the authors acknowledged IBM in their paper.<BR/>Even if there exists an employment relationship, does it mean that anything the employee does is necessarily at least partially supported by the employer?<BR/><BR/>I didn't check. So Einstein's papers should acknowledge the Swiss Patent office?<BR/><BR/>XAnonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1116387286216692432005-05-17T22:34:00.000-05:002005-05-17T22:34:00.000-05:00The NSF posting that Luca mentions in his comment ...The NSF posting that Luca mentions in his comment contains an error of omission that, in my opinion, is unconscionable.<BR/><BR/>The 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. <BR/><BR/>This kind of half truth in reporting from the most significant government organization devoted to supporting basic science is plainly disgusting.<BR/><BR/>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. <BR/><BR/>--D. Sivakumar<BR/>(I work for IBM, but that's not why I wrote this comment.)Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1116382572243415092005-05-17T21:16:00.000-05:002005-05-17T21:16:00.000-05:00There is an overall problem of funding in computer...There 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. <BR/><BR/>Adjusted 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. <BR/><BR/>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).<BR/><BR/><BR/>In any case, this is an extremely successful time for our field (think that just in the last few <I>months</I>, and just staying within <I>complexity</I>, 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.<BR/><BR/>LucaAnonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1116374982634746512005-05-17T19:09:00.000-05:002005-05-17T19:09:00.000-05:00I do agree that NSF funds more of applied research...I 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.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1116372363899547422005-05-17T18:26:00.000-05:002005-05-17T18:26:00.000-05:00The last comment was by me. --BoazThe last comment was by me. --BoazAnonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1116372346381169402005-05-17T18:25:00.000-05:002005-05-17T18:25:00.000-05:00Just to clarify, I don't think we (or anyone) dese...Just to clarify, I don't think we (or anyone) <I>deserve</I> government funding.<BR/><BR/>The issue is that the mission of theoretical computer science is very important and should be funded at a better level.<BR/><BR/>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.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1116368318854590562005-05-17T17:18:00.000-05:002005-05-17T17:18:00.000-05:00"Boo hoo hoo. Now you know what professors in the ..."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...."<BR/><BR/>Yes, 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.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1116367093889647992005-05-17T16:58:00.000-05:002005-05-17T16:58:00.000-05:00Boo hoo hoo. Now you know what professors in the m...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....Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1116366553392895392005-05-17T16:49:00.000-05:002005-05-17T16:49:00.000-05:00the TCS community might be well served by hiring a...<I>the TCS community might be well served by hiring a lobbyist. </I><BR/><BR/>Isn't ACM/USA supposed to play this role? Perhaps what is needed is more volunteers participating in that body. <BR/><BR/>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:<BR/><BR/>-LP interior point methods<BR/><BR/>-PKC<BR/><BR/>-NP-completeness<BR/><BR/>plus one particularly useful example from each of:<BR/><BR/>-approximation schemes<BR/><BR/>-randomized algorithms<BR/><BR/>-network algorithms<BR/><BR/>-spectral analysis (a la page ranking)<BR/><BR/>-indexing<BR/><BR/>-matching algorithms<BR/><BR/>-network flows<BR/><BR/>-interactive proofs<BR/><BR/>-quantum computing<BR/><BR/>-....Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1116361542531852282005-05-17T15:25:00.000-05:002005-05-17T15:25:00.000-05:00We can also learn something from AMS in this regar...We can also learn something from AMS in this regard. See <BR/>http://www.ams.org/government/congressfellowaward.htmlAnonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1116346105822007242005-05-17T11:08:00.000-05:002005-05-17T11:08:00.000-05:00I agree with Boaz. In this day and age, a good re...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. <BR/><BR/>Indeed, the TCS community might be well served by hiring a lobbyist. <BR/><BR/>I hear Jeff Vitter's brother is a congressman. Maybe you can turn to him for some advice...Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1116343178794408282005-05-17T10:19:00.000-05:002005-05-17T10:19:00.000-05:00Regarding the first commenter:I realize you were j...Regarding the first commenter:<BR/>I realize you were joking, but it's important to understand that the lack of funding is <B>not</B> because we don't have immediate applications.<BR/><BR/>For example, through one of the Link's in Lances post a few days ago, I saw DARPA's definition of basic science: <I>"systematic study directed toward greater knowledge or understanding of the fundamental aspects of phenomena and of observable facts without specific applications in mind." </I><BR/><BR/><BR/>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. <BR/><BR/>Moreover, people in Washington do understand that, and the theory funding problem is <B>not</B> 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.<BR/><BR/>-- BoazAnonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1116341487260224182005-05-17T09:51:00.000-05:002005-05-17T09:51:00.000-05:00Very interesting post. I was not aware that there ...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.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1116289040115770112005-05-16T19:17:00.000-05:002005-05-16T19:17:00.000-05:00Here's a wacko idea:How about changing the name of...Here's a wacko idea:<BR/><BR/>How about changing the name of the field? <BR/><BR/>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).Anonymousnoreply@blogger.com