tag:blogger.com,1999:blog-3722233.post3228966270379272028..comments2019-11-20T05:21:31.299-05:00Comments on Computational Complexity: Still Typecasting from DagstuhlLance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger4125tag:blogger.com,1999:blog-3722233.post-9374466397204703122018-10-07T16:57:52.354-04:002018-10-07T16:57:52.354-04:00For the record:
- Yes, my best guess is that it w...For the record:<br /><br />- Yes, my best guess is that it will take another 50 years to prove L = RL, but I'm not confident it will take that long. I consider it plausible that someone will discover a proof tomorrow.<br /><br />- I wouldn't be surprised if someone discovered a proof that RL is contained in DSPACE((log n)^{1 + o(1)}) within the next 10 years.William Hozahttps://williamhoza.comnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-24000716866536807022018-10-01T08:40:46.577-04:002018-10-01T08:40:46.577-04:00I've invented Complex Programming: Optimizatio...I've invented Complex Programming: Optimization of real-valued <br />complex functions over subsets of the complex plane:<br /><br />http://vixra.org/abs/1809.0601<br />Yuly Shipilevskyhttps://www.blogger.com/profile/13699450530150796472noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-75621528452136887342018-09-27T08:36:23.489-04:002018-09-27T08:36:23.489-04:00My only hit after googling "How old is Bill G...My only hit after googling "How old is Bill Gasarch?" is https://theresawelchy.wordpress.com/2018/09/26/still-typecasting-from-dagstuhl/domhttps://www.blogger.com/profile/05790539025733385232noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-16295269179307889982018-09-27T03:18:40.983-04:002018-09-27T03:18:40.983-04:00Let me just set the record straight, regarding my ...Let me just set the record straight, regarding my talk on MCSP.<br /><br />I don't think it's accurate to say "Allender did show that under projections [MCSP] isn't NP-complete" ... although I did mention the very nice result of Cody Murray and Ryan Williams, which says that MCSP is not NP-hard under log-time-computable local reductions (in which each each bit of the output is computable in logarithmic time if one has random access to the bits of the input. [In fact, the [Murray, Williams] result is much stronger than that, showing that PARITY is not reducible to MCSP in this way, even with as much as (nearly) n^{.5} time. They even generalize this to probabilistic reductions.]<br /><br />But it's still open if MCSP is NP-hard under projections, even if those projections are very uniform (such as the first-order projections that Neil Immerman has studied in depth). In fact, a problem closely related to MCSP, known as MKTP is actually hard for DET under nonuniform NC^0 reductions that are "nearly" projections. (In a paper I wrote with Manindra Agrawal and Steven Rudich, we call them "superprojections".) Thus, if one were able to prove that MKTP is not NP-complete under superprojections, then one would have separated NP from DET. I think that it will probably be difficult to show that MCSP is not NP-complete under nonuniform projections, but it might well be possible to show that it's not NP-complete under first-order projections. In fact, I think that would be a fantastic theorem.<br /><br />While I'm writing, let me say a few words about what I DID say in my Dagstuhl talk:<br /><br />I have been working with two fantastic undergraduates: Rahul Ilango (from Rutgers) and Neekon Vafa (from Harvard). Both participated in the DIMACS REU program. We have been studying the problem of approximating circuit size to within a small multiplicative factor; let's call this problem GapMCSP. We show that GapMCSP is not hard for NP (or even for any complexity class containing PARITY) under AC^0 reductions that make a bounded number of queries. (Our results are actually somewhat stronger than that, but I'm trying to keep this comment somewhat non-technical.) In contrast, most prior work reducing problems to MCSP carry through even for approximations to GapMCSP with very large multiplicative factors. (Provably, those results require reductions that are much more powerful than AC^0.)Eric Allenderhttps://www.blogger.com/profile/07417405562053586552noreply@blogger.com