tag:blogger.com,1999:blog-3722233.post3705294996875785193..comments2023-02-08T10:05:26.048-06:00Comments on Computational Complexity: CCC12: Post 1 of nLance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger3125tag:blogger.com,1999:blog-3722233.post-6776275233121574462012-07-20T09:33:11.197-05:002012-07-20T09:33:11.197-05:00Hello Harry, some people would argue that your com...Hello Harry, some people would argue that your comment is based on a misunderstanding of the current situation of the field.<br />Read for instance this earlier post and some of the comments:<br />blog.computationalcomplexity.org/2011/11/death-of-complexity-classes.htmlPascalhttps://www.blogger.com/profile/14201150679841329835noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-53811278060513492692012-07-19T02:35:20.074-05:002012-07-19T02:35:20.074-05:00Although I am just beginning my Phd, I was always ...Although I am just beginning my Phd, I was always fascinated by "old school" complexity theory, perhaps more than it is "healthy" for my scientific judgement. As a young researcher that draws its future carreer, it is clear to me why people avoid the "big questions" that are mostly purely theoretical. Those reasons however are primarily not scientific based but financial, either personal or department wide. Most researchers would prefer a solid record of publications, rather than 5 years spent on a theoretical matter, which might not produce any publishable results in the end. Furthermore, you can't blame a department head/dean/commitee for rejecting a grant for this type of long-term research, that might be required to solve difficult problems on complexity theory.<br /><br />Complexity theorists know the importance of time you dedicate to a problem, perhaps better than anyone. We know that some of the interestings ones have long proofs that require a lot of time to be written, refined and validated. As an example, I refer you to what Mulmuley has to say about veryfying a proof of P =/= NP. <br /><br />Perhaps research centers like Simons, can use the reputation of accomplished computer scientists to create research and student positions on pure structural complexity theory. Personally, I think it's time we looked thoroughly on the results from 1965 to 1980, update them to today's circumstances and continue the line of research that has been slowed down, if not halted since the late 80's.Anonymoushttps://www.blogger.com/profile/09364120444779754928noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-30377502655282077412012-07-16T16:04:48.833-05:002012-07-16T16:04:48.833-05:00In his talk Ryan said that he needed the kind of c...<i>In his talk Ryan said that he needed the kind of complexity that only people like Dick Lipton still remember.</i><br /><br />That's kind of a misquote :) What I said was something like: "can we improve the QBF lower bounds by using tools developed in, say, the last 20 years?... you know, things that people other than Dick know about." <br /><br />But it is true that things like the proof that Circuit Evaluation is in n*poly(log n) time on multitape Turing machines seem to require an archaeological expedition in the library... or several clever thoughts about sorting... or Dick as a co-author. <br /><br />This is unfortunate. How will we ever prove that SAT isn't in n*poly(log n) time on RAMs if we don't know how to prove it for multitape Turing machines? And how will we ever prove that if we forget all those neat constructions from the 70's?ryanwhttps://www.blogger.com/profile/09644595632189419277noreply@blogger.com