tag:blogger.com,1999:blog-3722233.post6202153192038609988..comments2019-10-21T21:47:16.813-04: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-21T08:14:09.421-05:002010-12-21T08:14:09.421-05: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-13T13:56:33.160-05:002010-11-13T13:56:33.160-05: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-12T13:28:32.107-05:002010-11-12T13:28:32.107-05: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-11T15:37:00.155-05:002010-11-11T15:37:00.155-05: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-10T09:03:38.500-05:002010-11-10T09:03:38.500-05: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-10T00:18:07.329-05:002010-11-10T00:18:07.329-05: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-09T23:38:38.083-05:002010-11-09T23:38:38.083-05: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-09T21:49:09.625-05:002010-11-09T21:49:09.625-05:00Why mod6?Why mod6?Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-37634499964179197872010-11-09T18:51:38.201-05:002010-11-09T18:51:38.201-05: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-09T13:27:13.583-05:002010-11-09T13:27:13.583-05: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