tag:blogger.com,1999:blog-3722233.post4400864623603224563..comments2021-04-09T08:39:40.083-05:00Comments on Computational Complexity: Is Ryan's Theorem Only Interesting to Complexity Theorists?Lance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger44125tag:blogger.com,1999:blog-3722233.post-44813953834434344092010-11-23T12:04:16.828-06:002010-11-23T12:04:16.828-06:00By the way, in all the recent discussion of ACC^0 ...<i>By the way, in all the recent discussion of ACC^0 I have seen, none has mentioned a characterization of ACC^0 that is very natural and intuitive and is part of a continuum that includes TC^0 as well:<br /><br />ACC^0 can be characterized as the class of the Boolean functions computable by polynomial-size constant depth unbounded fan-in arithmetic circuits over finite fields.</i><br /><br />This is probably the nicest characterization of ACC0 known. For those interested, the reference is: Agrawal, Allender, Datta, "On TC0, AC0, and Arithmetic Circuits".<br /><br />- Not Agrawal, Allender, or DattaAnonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-40237692483132136322010-11-22T13:37:14.466-06:002010-11-22T13:37:14.466-06:00Unfortunately, the so-called "advances" ...<i>Unfortunately, the so-called "advances" in complexity theory are advances only in the eyes of complexity theorists. Ryan's theorem is of interest to a handful of people who earn their bread and wine by doing similar things. To the rest of the world, these "advances" make little sense and have little effect.</i><br /><br />Would you apply the same argument to every advance in math, theoretical physics, astronomy, and other fields without immediate applications?<br /><br />If not, then how do you justify the double-standard?<br /><br />If so, then why do you spend your time reading an academic blog?Scotthttps://www.blogger.com/profile/13456161078489400740noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-86061945210040221762010-11-22T09:18:06.024-06:002010-11-22T09:18:06.024-06:00That's why we are so excited about this paper....<i> That's why we are so excited about this paper.</i><br /><br />I don't think that you've really captured why I find Ryan's result so interesting. It is <i>not</i> that it proves the specific lower bounds for ACC^0. It is the fact that it strongly validates the fascinating new approach that Ryan sketched in his STOC paper, a fundamentally new idea about how to approach circuit lower bounds for uniform exponential-time complexity classes. (Indeed the result in some sense seems less about ACC^0 than about NEXP.)<br /><br />By the way, in all the recent discussion of ACC^0 I have seen, none has mentioned a characterization of ACC^0 that is very natural and intuitive and is part of a continuum that includes TC^0 as well:<br /><br />ACC^0 can be characterized as the class of the Boolean functions computable by polynomial-size constant depth unbounded fan-in arithmetic circuits over finite fields. <br /><br />If one allows the size of the field to grow as a function of the number of input bits then TC^0 can be characterized as Boolean function computable by such circuits when the field size grows anywhere from <br />log^Omega(1) n to n^O(1).Paul Beamenoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-89584605624665664762010-11-22T07:29:28.309-06:002010-11-22T07:29:28.309-06:00@Anon 12:15 AM, November 22, 2010
It seems that y...@Anon 12:15 AM, November 22, 2010<br /><br />It seems that you have forgotten that complexity theory is part of THEORETICAL computer science. Comparing it to HCI and other applied CS is like comparing apples to oranges. I can criticize HCI based on those criteria we have in TCS but that does not mean much, right? Your comment is a little bit insulting to me, just to get the feeling, would you like me say HCI is engineering and not computer *science*?Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-30055399721586940512010-11-22T00:15:38.703-06:002010-11-22T00:15:38.703-06:00Unfortunately, the so-called "advances" ...Unfortunately, the so-called "advances" in complexity theory are advances only in the eyes of complexity theorists. Ryan's theorem is of interest to a handful of people who earn their bread and wine by doing similar things. To the rest of the world, these "advances" make little sense and have little effect. If someone asks me how will Intel's advances in gesture recognition technology will affect him/her, I can give a convincing answer. But if someone asks me how will Ryan's theorem affect him/her, I won't be able to say anything sensible. And I think even Ryan will not be able to give a convincing answer. -- guptillAnonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-14567428604917469812010-11-21T12:38:11.754-06:002010-11-21T12:38:11.754-06:00Some peopel mentioned that Willimas
lower bound wa...Some peopel mentioned that Willimas<br />lower bound was derived from combining<br />some existing results. I would like<br />emphasis that William's main contribution is the new philosophy for proving lower bound via upper bound. This method will be much more<br />important than Razeborov's approximation method.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-22609083960311306472010-11-19T17:01:28.421-06:002010-11-19T17:01:28.421-06:00I think I have a decent high-level understanding o...I think I have a decent high-level understanding of this paper now, thanks to some inspired talks by Pavan Aduri over the last two weeks, and some of the criticisms left on this blog are missing the point.<br /><br />The results in the Williams paper are obtained through remarkable breadth and cleverness, as opposed to the depth of original arguments. The author combines several known results in a novel way, and the circuit lower bounds follow directly from that novel combination. This feels different to me from, say, Razborov's method of approximations, which to my naive eye looks as though it came out of nowhere -- that paper/technique seems more "deep" than "broad."<br /><br />I'm sure some people will take this as a slam against complexity theory, or against Ryan Williams, because I am saying the new result is broader than it is deep, but I mean it as a compliment to both him and the field, and I think it should be taken that way. What Williams has shown is that <i>all the ingredients were already there</i>, that work done on fast matrix multiplication, on the SYM+ characterization of ACC circuits, etc., once they were viewed with the new eyes he brought to the problem. Among other things, this implies that <i>there has been steady advancement in circuit lower bounds over the last twenty years</i> because Williams crafts a jigsaw of puzzle pieces/theorems proved during that time period.<br /><br />Rather than this being the breakthrough showing all those other schmoes were wrong, it is more a confirmation that a lot of people have been on the right track.Aaron Sterlingnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-28355231205253484752010-11-19T13:01:49.777-06:002010-11-19T13:01:49.777-06:00So we should stop claiming that we are making prog...<i>So we should stop claiming that we are making progress towards solving P vs NP by proving lowerbounds for very weak models of computation.</i><br /><br />That circuits lower bounds can prove P!=NP is a joke, I agree completely. A sentence in grants, no more. This is clearly not the goal of circuit complexity. Many bright brains (Kolmogorov among them) even conjectured that all P can be done by linear size circuits. But should humans first try to go to the moon before they have tried to discover the wheel?Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-58420416421906371392010-11-19T11:31:33.686-06:002010-11-19T11:31:33.686-06:00Last anon, that was hilarious.
No, it is not abou...Last anon, that was hilarious.<br /><br />No, it is not about time, it is about what is the intelligent thing to do. Scientists in NASA were not climbing to the trees as a first step towards going to the moon, similarly proving lowerbounds for very weak models of computation like constant depth circuits is not the right step towards separating P vs NP. So we should stop claiming that we are making progress towards solving P vs NP by proving lowerbounds for very weak models of computation.<br /><br />Creating programs which were capable of very limited amount of intelligence (even less than a monkey) and claiming that the ultimate goal is human-like intelligence and it is achievable in near future is just bogus.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-73694322648023788892010-11-19T08:00:46.828-06:002010-11-19T08:00:46.828-06:00The monkeys that climbed the highest trees develop...The monkeys that climbed the highest trees developed an advantage, evolved in to humans, then went to the moon. I don't get the allegory. Perhaps it is a statement about time?Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-25270510608925304132010-11-19T05:44:13.405-06:002010-11-19T05:44:13.405-06:00I am surprised about a strongly negative reaction ...I am surprised about a strongly negative reaction to my "innocent" doubt concerning our *allocation*, not the *merits* of the result. Concerning Lance's post, not Ryan's result itself. Concerning the difference between structural and circuit complexity. Do you guys really think there is no difference?Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-90576712839127137242010-11-18T17:25:05.267-06:002010-11-18T17:25:05.267-06:00@John Sidle:
Ketan's argument isn't very...@John Sidle: <br /><br />Ketan's argument isn't very good. Here it is in a nutshell:<br /><br />"Provided that we include things that are not normally considered complexity and that do not use the methods of complexity then complexity is doing ok".<br /><br />Pretty weak, don't you think?<br /><br />I do believe it is high time that complexity examines its lack of progress over the last twenty years yet I'm equally surprised that all of these negative comments about complexity come out now when <i>finally</i> some progress has been made.<br /><br />Ryan's result is a breakthrough and the first hint that complexity might yet start to move again after the last two decades of stasis.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-60833382567669671902010-11-18T11:11:09.117-06:002010-11-18T11:11:09.117-06:00why don't you yourself show that majority is n...<i>why don't you yourself show that majority is not in ACC?</i><br /><br />Would like to do this :-) I even hope this could be done using graph complexity, albeit for a little bit more complex function whose communication matrix has many ones but no 2x2 all-1 submatrices. <br /><br />But more seriously: Ryan's result is indeed a great separation of two complexity classes, no doubts. B.t.w. recently there were some other intriguing separations, like that of the communication complexity classes \Sigma_2 and UPP (unbounded-error PP) done by Razborov and Sherstov. My only "complain" is that we call Ryan's nice result a breakthrough in *circuit* (not in *structural*) complexity. I think these are quite different fields, both by the nature of problems and techniques used. In structural complexity one tries to answer more global questions, like is space a more powerful resource than time, etc. Whereas in circuit complexity one tries (at least I try) to answer more "pragmatic" questions like that about the Majority. Hence, a difference in techniques used.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-39688547351805477102010-11-17T22:49:36.421-06:002010-11-17T22:49:36.421-06:00@John Silde
PS: I am personally very excited abou...@John Silde<br /><br />PS: I am personally very excited about Ryan's result and expect stronger results from him (or based on his work) in near future (and hopefully no new barriers).Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-77152879286994470162010-11-17T22:43:10.642-06:002010-11-17T22:43:10.642-06:00John sidles, you haven't understood my comment...John sidles, you haven't understood my comment. Please reread it, I am not saying complexity theory has been pathetic, I was trying to explain why non-complexity theorists are not excited about this result and Lance post is not going to change it.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-60296374700238677302010-11-17T18:13:25.344-06:002010-11-17T18:13:25.344-06:00SJ, we all know it's you.
why don't you y...SJ, we all know it's you.<br /><br />why don't you yourself show that majority is not in ACC?Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1197606042010822492010-11-17T09:08:17.178-06:002010-11-17T09:08:17.178-06:00Anonymous says: "Complexity theory [has] been...<b>Anonymous says:</b> <i>"Complexity theory [has] been in a pathetic and embarrassing state with no progress in last two decades until last week, now it is *a tiny bit* less embarrassing."</i><br /><br />As Ketan Mulmuley has been emphasizing, this statement is *not* true ... <i>provided</i> that we recognize that one of the key questions in complexity theory is "How big is the class <i>P?"</i><br /><br />If we measure progress in complexity theory by the size of the class of problems that have been demonstratedâ€”either rigorously or empiricallyâ€”to be solvable in <i>P,</i> then the growth of this class has been truly spectacular, and shows no signs of slowing, and very few fundamental limits to continued growth are known.<br /><br />Indeed, it can be argued that a truly great achievement of complexity theory in the past three decades has to establish that there are surprisingly few (hmmmm ... any?) foreseeable limits to continued expansion in the size of the class of problems in <i>P</i>.John Sidleshttp://www.mrfm.orgnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-58449067643992893522010-11-16T14:44:26.388-06:002010-11-16T14:44:26.388-06:00I don't understand this complaint: if you want...<i>I don't understand this complaint: if you want an explicit function that is hard for ACC, just take any NEXP-complete function...</i><br /><br />But what about this: Is Majority in ACC? Is Multiplication of two n-bit numbers there? Does this result answers these questions?Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-13120587914790331132010-11-16T04:01:27.567-06:002010-11-16T04:01:27.567-06:00Very poor metaphor Scott! Even you can do better.Very poor metaphor Scott! Even you can do better.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-71321322079589564142010-11-16T01:22:05.670-06:002010-11-16T01:22:05.670-06:00Modern complexity theory suffers from being simult...Modern complexity theory suffers from being simultaneously so abstract as to be absolutely useless in real life, yet so complicated as to require pages and pages just to define.<br /><br />IMHO further breakthroughs in complexity theory will need to come from a totally fresh standpoint, a revolution or something. To an outsider, it seems you guys are just making longer and longer acronyms, conjecturing whether N-COMP-EXP-SPACE-CLOSURE-PRIME is equivalent to NP-PRECOMP-HARD-REDUCIBLE and so on.<br /><br />In fairness, it sounds like Ryan's result is more useful in real life than, say, Fermat's Last Theorem, and we all know how excited that made everyone. Again, though, FLT doesn't take pages to define...Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-48467752964181926202010-11-15T17:02:49.526-06:002010-11-15T17:02:49.526-06:00"I don't understand this complaint"
..."I don't understand this complaint"<br /><br /><a href="http://rjlipton.wordpress.com/2010/11/08/a-breakthrough-result/#comment-8309" rel="nofollow">See this discussion.</a>Mitchellhttps://www.blogger.com/profile/10768655514143252049noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-72706610081409994882010-11-15T16:10:50.176-06:002010-11-15T16:10:50.176-06:00For those trying to find *explicit* hard functions...<em>For those trying to find *explicit* hard functions? Not just to show their existence in some huge sets. </em><br /><br />I don't understand this complaint: if you want an explicit function that is hard for ACC, just take any NEXP-complete function...Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-67709205216805597002010-11-15T14:43:15.983-06:002010-11-15T14:43:15.983-06:00Is Ryan's Theorem Only Interesting to Complexi...<i>Is Ryan's Theorem Only Interesting to Complexity Theorists?</i><br /><br />This "only" is somewhat too "arrogant". Let us ask: is it interesting for people working in circuit complexity? For those trying to find *explicit* hard functions? Not just to show their existence in some huge sets. <br /><br />Let us separate things: this is perhaps a great result in *structural* complexity, but not in *circuit* complexity.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-8352886620876137822010-11-15T14:20:18.275-06:002010-11-15T14:20:18.275-06:00The going to the moon metaphor by McCarty doesn...The going to the moon metaphor by McCarty doesn't seem to work. The point of that metaphor is that if you want to go to the moon, the first step is not climbing trees. That metaphor would only be appropriate only if you had reasons to think that the method developed by Ryan is not going to go far in solving P vs NP. I don't see any reason for this at the moment.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-36847854104910784432010-11-15T14:14:25.778-06:002010-11-15T14:14:25.778-06:00It is already hard to see why Razborov and Smolens...<i>It is already hard to see why Razborov and Smolensky result is interesting ...</i><br /><br />When climbing, monkeys learn new climbing techniques. And R&S gave us one more of them: approximation by low degree polynomials. We want "great" results without having a "great toolbox". Want quickies without long, long study of "small" problems. Counting, diagonalization and the like will not help monkeys much ... They need real mathematics.Anonymousnoreply@blogger.com