tag:blogger.com,1999:blog-3722233.post116168885714463650..comments2024-02-26T20:37:24.042-06:00Comments on Computational Complexity: FOCS Funding, Music and TalksLance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger17125tag:blogger.com,1999:blog-3722233.post-1161953505493654522006-10-27T07:51:00.000-05:002006-10-27T07:51:00.000-05:00The original post had stated that Bill Steiger had...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.Lancehttps://www.blogger.com/profile/10719117059849994105noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1161805437814954642006-10-25T14:43:00.000-05:002006-10-25T14:43:00.000-05:00There is no formula according to which NSF *ought*...There is no formula according to which NSF *ought* to distribute its budget.<BR/><BR/>NSF's mission is to promote scientific research, and not to equally distribute grants accross all faculty.<BR/><BR/>The question is whether spending more than 1-2% on theory will advance scientific research.<BR/><BR/>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.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1161759531499439012006-10-25T01:58:00.000-05:002006-10-25T01:58:00.000-05:00@number 9, so you are saying once we reach to depa...@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.<BR/><BR/>Further, 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).<BR/><BR/>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? <BR/><BR/>Could somebody, let us say at Berkeley, confirm what fraction of grad-students have to do TA ship in theory vs non-theory?Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1161754217545441802006-10-25T00:30:00.000-05:002006-10-25T00:30:00.000-05:00(cough cough)VV isolation lemma (cough cough)(cough cough)<BR/><BR/>VV isolation lemma <BR/><BR/>(cough cough)Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1161753945538177792006-10-25T00:25:00.000-05:002006-10-25T00:25:00.000-05:00Valiant's #SAT mod 7 result is for formulas of the...Valiant'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. <BR/><BR/>Valiant'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.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1161748815652151792006-10-24T23:00:00.000-05:002006-10-24T23:00:00.000-05:00Isn't funding also skewed highly towards the tier ...Isn't funding also skewed highly towards the tier 1 universities?Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1161743433558315872006-10-24T21:30:00.000-05:002006-10-24T21:30:00.000-05:00The result about #SAT mod 7 is claimed in referenc...The result about #SAT mod 7 is claimed in reference [17] <A HREF="http://www.cs.wisc.edu/~jyc/papers/symmetric-sig.ps" REL="nofollow">here</A>.<BR/><BR/>However, the result does not seem to say that #SAT mod 7 is in P, but something more restrictive.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1161741298357150372006-10-24T20:54:00.000-05:002006-10-24T20:54:00.000-05:00I just want to check that when you reportedon Vali...I just want to check that when you reported<BR/>on Valiant's paper you weren't making a typo:<BR/><BR/>1) Does he REALLY thing NC^2 = P^{#P} ???<BR/><BR/>2) Is determining if #SAT \equiv 0 mod 7<BR/>REALLY in P ???<BR/><BR/>Please verify and link.<BR/>bill gasarchGASARCHhttps://www.blogger.com/profile/06134382469361359081noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1161735553783034562006-10-24T19:19:00.000-05:002006-10-24T19:19:00.000-05:00Just to second the comments of anonymous 8, the fr...Just 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).Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1161731663707241292006-10-24T18:14:00.000-05:002006-10-24T18:14:00.000-05:00Departments below a certain "threshold" do not mak...Departments 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".Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1161725539261702872006-10-24T16:32:00.000-05:002006-10-24T16:32:00.000-05:00Are we to assume that "top ten" makes up our commu...Are we to assume that "top ten" makes up our community? Some sense of community, that.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1161725122351007102006-10-24T16:25:00.000-05:002006-10-24T16:25:00.000-05:00Did you mean: terry sejnowskiDid you mean: terry sejnowskiAnonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1161724750587219812006-10-24T16:19:00.000-05:002006-10-24T16:19:00.000-05:00Take the number of faculty members at top-10 resea...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.Lucahttps://www.blogger.com/profile/17835412240486594185noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1161721997031806132006-10-24T15:33:00.000-05:002006-10-24T15:33:00.000-05:00Anon, 3:19pm: I am just guessing, but I think 20% ...Anon, 3:19pm: I am just guessing, but I think 20% comes from this sentence:<BR/><BR/>"Of the ~500 CS proposals to NSF, about 90-100 were for Theory."<BR/><BR/>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%.)<BR/><BR/>AndrisAnonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1161721199360276942006-10-24T15:19:00.000-05:002006-10-24T15:19:00.000-05:00What is the basis of this 20% number? It may hold ...What is the basis of this 20% number? It may hold true for some concrete universities, but it's very unlikely to be true worldwide.<BR/><BR/>As 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.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1161716315802320152006-10-24T13:58:00.000-05:002006-10-24T13:58:00.000-05:00Got a link to the #SAT%7 paper? That would be a gr...Got a link to the #SAT%7 paper? That would be a great pre-processor...Chad Brewbakerhttps://www.blogger.com/profile/10443154815748267611noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1161715952724796402006-10-24T13:52:00.000-05:002006-10-24T13:52:00.000-05:00Bill Steiger is working hard for a change.I found ...<EM>Bill Steiger is working hard for a change.</EM><BR/><BR/>I found this comment quite hilarious. It sounds as though Bill Steiger usually does not work hard, and is doing so for a change :-)Anonymousnoreply@blogger.com