A few years ago, there was some work by Joel Friedman relating lower circuit bounds to Grothendieck cohomology (see papers: http://arxiv.org/abs/cs/0512008, http://arxiv.org/abs/cs/0604024). Has this line of thought brought any new insights into boolean complexity, or does it remains rather a mathematical curiosity?
$\begingroup$
$\endgroup$
1
-
4$\begingroup$ I'm very curious to see the answer to this. Of course, the easiest would be to email Joel Friedman :) $\endgroup$– Suresh VenkatCommented Apr 6, 2011 at 2:36
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
7
I corresponded with Joel Friedman about 3 years ago on this topic. At the time he said that his approach had not led to any significant new insights into complexity theory, though he still thought it was a promising tack.
Basically, Friedman tries to rephrase the problems of circuit complexity in the language of sheaves on a Grothendieck topology. The hope is that this process will allow geometric intuition to be applied to the problem of finding circuit lower bounds. While it's certainly worth checking to see if this path leads anywhere, there are heuristic reasons to be skeptical. Geometric intuition works best in the context of smooth varieties, or things that are sufficiently similar to smooth varieties that the intuition doesn't totally break down. In other words, you need some structure in order for geometric intuition to gain a foothold. But circuit lower bounds by their very nature must confront arbitrary computations, which are difficult to analyze precisely because they seem to be so structureless. Friedman admits right up front that the Grothendieck topologies he considers are highly combinatorial, and far removed from the usual objects of study in algebraic geometry.
As a side comment, I'd say that it's important not to get too excited about an idea just because it uses unfamiliar, high-powered machinery. The machinery might be very effective at solving the problems that it was designed for, but for it to be useful for attacking a known hard problem in another domain, there needs to be some compelling argument why the foreign machinery is well adapted to address the fundamental obstacle in the problem of interest.
-
4$\begingroup$ 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. $\endgroup$ Commented Apr 6, 2011 at 15:53
-
2$\begingroup$ @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. $\endgroup$ Commented Apr 6, 2011 at 17:23
-
$\begingroup$ 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) $\endgroup$ Commented Apr 7, 2011 at 2:27
-
1$\begingroup$ @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. $\endgroup$– 5501Commented Apr 8, 2011 at 14:24
-
1$\begingroup$ @Neel, I don't have an answer, but I wonder if this might merit a question of its own. $\endgroup$ Commented Apr 13, 2011 at 15:48
$\begingroup$
$\endgroup$
0
I think Timothy Chow has it exactly right. I have my own personal laundry list of ideas involving "smooth" varieties, or concepts like counting connected components or monomials that go with the bottom few rungs of the "cohomology ladder"---all of them shown not to be hardness predicates by (variations on) the Mayr-Meyer construction showing EXPSPACE-completeness of various GCT-related problems. My one riff on his last paragraph is that I think some kind of high-powered machinery is needed...!
