tag:blogger.com,1999:blog-3722233.post8613706651628736734..comments2024-03-27T19:58:17.387-05:00Comments on Computational Complexity: Is Moore's Law Good for CS?Lance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger12125tag:blogger.com,1999:blog-3722233.post-41992342900568627542014-03-28T14:25:52.872-05:002014-03-28T14:25:52.872-05:00It's a funny question to ask, whether a law is...It's a funny question to ask, whether a law is good or bad for a field. Is gravity good for physics? Even if you said "no" (and that would be an interesting defense!), it's not like you could do anything about it.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-5526158913195803582012-05-09T07:04:07.784-05:002012-05-09T07:04:07.784-05:00I find your negative connotation about hackers to ...I find your negative connotation about hackers to be frustrating. It is this hacking which has lead to many improvement in the CS world.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-50340731719344357292012-05-06T18:23:23.765-05:002012-05-06T18:23:23.765-05:00Moore's law is very good for CS. The most impo...Moore's law is very good for CS. The most important effect is probably not increasing the maximum speed to solve a problem, but decreasing the minimum price. Remember that in the 1960s, there were a host of "expensive" programs at the cutting edge: the expensive typewriter, the expensive desk calculator, the expensive planetarium, the expensive tape recorder. Many things were just barely possible on the computers of the 1960s, but economically indefensible.<br /><br />As the cost of computers and computation comes down, more things get turned into computer science problems. Let the boring problems get solved through better hardware, they keep making more of the interesting problems.Snarkyxanfnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-78514883844601100532012-05-02T19:59:23.152-05:002012-05-02T19:59:23.152-05:00@ Previous anons: No one said anything about const...@ Previous anons: No one said anything about constants and log log factors, you are the ones who brought all that up. Lance's comment is no more snobbish than Dijsktra's famous quote "Computer science is no more about computers than astronomy is about telescopes." Computer science is the study of problem solving techniques, and this is distinct from computer engineering. Clearly there is a spectrum and much work falls somewhere in between, and some exceptional work isn't well described this way at all. But that doesn't make it snobbish to draw a distinction between computer science and computer engineering.<br /><br />@Anon 1: It isn't feasible to give a tight analysis of an algorithm down to the level of constants, for problems significantly more complicated than median finding. Also it isn't particularly meaningful since that detail is lost in Church-Turing equivalences. If you can write a paper that gets down to the level of constants that is interesting at a high level and isn't just a tome of tedious detail, people may still read it. But it's a tall order. I don't think pinning down the runtime constants is likely to be the next frontier as you seem to suggest.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-3841000816048656592012-05-01T11:14:12.372-05:002012-05-01T11:14:12.372-05:00Is getting constants down "hacking" beca...Is getting constants down "hacking" because if it is then a bunch of "theory" work on median finding needs to get demoted.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-55975568388799135732012-05-01T07:27:57.514-05:002012-05-01T07:27:57.514-05:00"Without the increased power of computers, we..."Without the increased power of computers, we all become hackers to make our programs run better and that is not computer science."<br /><br />Because shaving a factor of log log n off the running time of an algorithm *is* computer science...Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-9396927689229030212012-04-30T19:11:03.104-05:002012-04-30T19:11:03.104-05:00Your dismissive attitude towards what you call &qu...Your dismissive attitude towards what you call "hacking" is disturbing. You sir are a "CS" snob.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-67317469659219444612012-04-30T11:42:14.783-05:002012-04-30T11:42:14.783-05:00Friedman is complaining that the advances in compu...Friedman is complaining that the advances in computer technology have been traded for more abstract general-purpose languages. This has been fantastic for theoretical computer science. The lost skills of hand-tuning exquisite data structures were the antithesis of the asymptotic-minded theoretical approach.Davidhttps://www.blogger.com/profile/13818371550669837787noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-81900631026621462012-04-30T10:43:25.664-05:002012-04-30T10:43:25.664-05:00Robert E Bixby's article "Solving Real-Wo...Robert E Bixby's article "Solving Real-World Linear Programs: A Decade and More of Progress" (<i>Operations Research</i>, 2002) surveys the balance between "Moore's Law" (that is, exponential) progress in computing power versus progress in algorithmic efficiency, and concludes that the two exponents are approximately equal. Good.<br /><br />More broadly, exponential technical progress is seen across broad spans of STEM capabilities that include:<br /><br />• algorithmic efficiency (see above),<br />• computational speed (see above),<br />• computational energy efficiency,<br />• channel capacity of data transmission, and<br />• channel capacity of data acquisition/sensing.<br /><br />An advance in any one of these areas helps all the others, and conversely (but slightly less obviously) obstructions and imbalances relating to progress in any one of these areas, in the long run, act to hinders all the others.<br /><br />In my own field of medicine, for example, progress is presently slowed by an imbalance between a burgeoning gene sequencing capacity — with costs dropping 10^6-fold in a generation — versus essentially fixed costs associated with data acquisition relating to the epigenomic mechanisms that regulate gene expression. To the extent that the economic and social vigor of the biomedical sector of the STEM community is compromised by the roadblock, everyone is adversely impacted (not just biomedical researchers, physicians, and their patients).<br /><br />Recalling that <i>Aergia</i> was the Greek Goddess of indolence, key STEM sectors that once were perceived as holding forth unbounded Moore's Law potentialities, that nowadays are perceived as afflicted (temporarily?) by <i>Aergia Syndrome</i>, readily come to mind:<br /><br />• epigenomic molecular biology,<br />• regenerative medicine,<br />• efficient code-writing,<br />• practical quantum computers,<br />• rigor within the Complexity Zoo, <br />• viable fusion power, and/or<br />– safe nuclear power, and/or<br />– cheap photovoltaic power, and/or<br />– "clean coal."<br /><br />However, Aergia Syndrome is perhaps most strikingly evident in STEM education. In recent decades the perceived value of a STEM education, relative to the costs and duration of that education, has not increased at anything approaching Moore's Law exponention. One wonders, why not? <br /><br />The increasing prevalence of Aergia Syndrome in STEM education is a tough, deep, vital question … and yet in-depth analyses of it are surprisingly hard to find.John Sidleshttps://www.blogger.com/profile/16286860374431298556noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-15229619171096991322012-04-30T09:16:44.729-05:002012-04-30T09:16:44.729-05:00I don't think the old notion of (practical) ef...I don't think the old notion of (practical) efficiency applies anymore anyway. Going forward the only way (or at least maybe the only proper way) to be "more efficient" is to take full advantage of parallel processing, multicore processors, etc. That means writing programs that are multi-threaded from day one.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-20405094033466014012012-04-30T09:06:43.604-05:002012-04-30T09:06:43.604-05:00Roy Friedman's argument reminds me of the Brok...Roy Friedman's argument reminds me of the Broken Window Fallacy.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-51713151089220159072012-04-30T08:25:16.378-05:002012-04-30T08:25:16.378-05:001. What if Moore's Law has concluded (ever non...1. What if Moore's Law has concluded (ever nonlinear advance per year in number of transistors per chip), but there are continued dramatic increases in power-efficiency and corresponding decrease in costs, leading to nonlinear growth per year in number of deployed chips? <br /><br />2. It's good to recall that once upon a time, only decidability mattered. What's that you're working on, satisfiability? Not interesting, it's decidable. We can look back and laugh, but who's to say that there won't be some beautiful theory of what you call hackers reducing the constants? Can you prove this won't be the case?Anonymousnoreply@blogger.com