tag:blogger.com,1999:blog-3722233.post6202153192038609988..comments2024-06-24T15:24:01.378-05:00Comments on Computational Complexity: A Breakthrough Circuit Lower BoundLance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger10125tag:blogger.com,1999:blog-3722233.post-64151751488667961072010-12-21T07:14:09.421-06:002010-12-21T07:14:09.421-06:00One thing I find worth noticing in the blog post i...One thing I find worth noticing in the blog post is the statement:<br /><br />"Ryan's proof doesn't use deep mathematical techniques but rather puts together a series of known tools in amazingly clever ways."<br /><br />Cleverness is often a key to breakthroughs in algorithm: sometimes a small twist makes a huge difference. However, some referees seem to think that papers need to have fundamental new technique: that a strong result doesn't do it.Mikkel Thoruphttps://www.blogger.com/profile/10495805784088145688noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-71676302043776299292010-11-13T12:56:33.160-06:002010-11-13T12:56:33.160-06:00I second the last "Anonymous": where is ...I second the last "Anonymous": where is the hard function? To call circuit lower bounds obtained by diagonalization and counting "breakthrough" seems somewhat too generous ... I don't say the result is not interesting: it is! But not in the same level with, say, Razborov's *explicit* lower bounds.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-23757091540174183192010-11-12T12:28:32.107-06:002010-11-12T12:28:32.107-06:00He uses "diagonalization", and we're...He uses "diagonalization", and we're calling that progress? Umm, no. Try again. Non-constructive proofs aren't worth the paper they're printed on.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-47018089879947831962010-11-11T14:37:00.155-06:002010-11-11T14:37:00.155-06:00What is NEXP? Could someone describe what just hap...What is NEXP? Could someone describe what just happened on a slightly less technical level?Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-22237883574805944722010-11-10T08:03:38.500-06:002010-11-10T08:03:38.500-06:00Anonymous 3: Razborov-Smolensky already showed tha...Anonymous 3: Razborov-Smolensky already showed that modp can't be computed by ACC with modq gates for p \neq q distinct primes. (And so NEXP is not in ACC with modp gates for p prime.) 6 is the smallest product of distinct primes.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-40071360748638318772010-11-09T23:18:07.329-06:002010-11-09T23:18:07.329-06:00Anonymous: ACC^0 supports multiple moduli. You can...Anonymous: ACC^0 supports multiple moduli. You can simulate mod_m and mod_n with mod_{m*n}. So as long as there are a constant number of such moduli, ACC^0 remains the same.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-7897168664897048882010-11-09T22:38:38.083-06:002010-11-09T22:38:38.083-06:00For mod_m and mod_n with different m and n, we can...For mod_m and mod_n with different m and n, we can replace the two types of gates with one gate mod_(mn).Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-48807408446174385252010-11-09T20:49:09.625-06:002010-11-09T20:49:09.625-06:00Why mod6?Why mod6?Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-37634499964179197872010-11-09T17:51:38.201-06:002010-11-09T17:51:38.201-06:00Maybe a silly question, but is anything known abou...Maybe a silly question, but is anything known about what happens to the class ACC^0 if we allow mod_m gates and mod_n gates for two distinct m, n?Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-69443304124364384952010-11-09T12:27:13.583-06:002010-11-09T12:27:13.583-06:00What a wonderful result. As a small aside, we actu...What a wonderful result. As a small aside, we actually think we do have one-way functions in ACC0 (and even NC0), I believe the open question is regarding pseudorandom functions.Anonymousnoreply@blogger.com