Timeline for Cohomological approach to boolean complexity
Current License: CC BY-SA 2.5
9 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Apr 13, 2011 at 16:46 | comment | added | Neel Krishnaswami | @Suresh: good idea. :) | |
| Apr 13, 2011 at 15:48 | comment | added | Suresh Venkat | @Neel, I don't have an answer, but I wonder if this might merit a question of its own. | |
| Apr 13, 2011 at 15:05 | comment | added | Neel Krishnaswami | Does the cohomological approach nicely model any of the heuristics people use in BDD libraries? I'm not so interested in lower bounds, but I am very interested in program structuring techniques involving cool math. (The only related work I know is Fiore's work on lambda-definability for lambda calculus with coproducts, which uses Grothendieck topologies to model splitting and pasting the branches of if-statements together. It's very interesting seeing a related idea in complexity.) | |
| Apr 8, 2011 at 14:24 | comment | added | 5501 | @Suresh: If you are talking about the Buergisser/Ikenmeyer paper, I think it tells much more about the limits of the GCT approach than about how to prove lower bounds. | |
| Apr 7, 2011 at 2:27 | comment | added | Suresh Venkat | indeed. it's interesting to see a STOC 2011 paper that uses GCT for matrix multiplication bounds (and Ketan had mentioned this result in his tutorial at FOCS) | |
| Apr 6, 2011 at 17:23 | comment | added | Timothy Chow | @Suresh: You're right that the Mulmuley-Sohoni approach is different, but the fundamental problem of coping with an arbitrary computation is still lurking in the background, so it is fair to ask just how one expects to come to grips with it. At the moment I don't think anybody really knows, which is why the GCT folks aren't promising spectacular breakthroughs any time soon. | |
| Apr 6, 2011 at 16:04 | vote | accept | Marcin Kotowski | ||
| Apr 6, 2011 at 15:53 | comment | added | Suresh Venkat | Of course Mulmuley's efforts are along "similar" lines in the sense of using "smooth structures", but he's looking at problems that admit nice geometric invariants to begin with. | |
| Apr 6, 2011 at 14:44 | history | answered | Timothy Chow | CC BY-SA 2.5 |