<p>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 <em>some</em> kind of high-powered machinery is needed...!</p>

CC BY-SA 3.0
2011-04-13T14:24:13.957Z
2011-04-13T14:24:13.957Z
Kenneth W. Regan
<p>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.</p>

<p>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 <i>structure</i> in order for geometric intuition to gain a foothold.  But circuit lower bounds by their very nature must confront <i>arbitrary computations</i>, 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.</p>

<p>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.</p>

CC BY-SA 2.5
2011-04-06T15:53:45.880Z
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.
Suresh Venkat
CC BY-SA 2.5
2011-04-06T17:23:36.953Z
@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.
Timothy Chow
CC BY-SA 2.5
2011-04-07T02:27:31.507Z
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)
Suresh Venkat
CC BY-SA 3.0
2011-04-08T14:24:32.897Z
@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.
5501
CC BY-SA 3.0
2011-04-13T15:05:00.077Z
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.)
Neel Krishnaswami
CC BY-SA 3.0
2011-04-13T15:48:54.530Z
@Neel, I don't have an answer, but I wonder if this might merit a question of its own.
Suresh Venkat
CC BY-SA 3.0
2011-04-13T16:46:02.947Z
@Suresh: good idea. :)
Neel Krishnaswami
CC BY-SA 2.5
2011-04-06T14:44:58.433Z
2011-04-06T14:44:58.433Z
Timothy Chow
<p>A few years ago, there was some work by Joel Friedman relating lower circuit bounds to Grothendieck cohomology (see papers: <a href="http://arxiv.org/abs/cs/0512008">http://arxiv.org/abs/cs/0512008</a>, <a href="http://arxiv.org/abs/cs/0604024">http://arxiv.org/abs/cs/0604024</a>). Has this line of thought brought any new insights into boolean complexity, or does it remains rather a mathematical curiosity?</p>

CC BY-SA 2.5
2011-04-06T02:36:36.237Z
I'm very curious to see the answer to this. Of course, the easiest would be to email Joel Friedman :)
Suresh Venkat
<cc.complexity-theory><lower-bounds><circuit-complexity><boolean-functions>
Cohomological approach to boolean complexity
Marcin Kotowski
# Cohomological approach to boolean complexity

(Asked by: username_0 on 2011-04-05)

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?

**Tags:** cc.complexity-theory, lower-bounds, circuit-complexity, boolean-functions
> **Comments:**
> **username_1**: I'm very curious to see the answer to this. Of course, the easiest would be to email Joel Friedman :)  

---

## 2 answers

### Answer by username_3 on 2011-04-06. Score: 28 | Accepted answer

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.

> **Comments:**
> **username_1**: 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.  
> **username_3**: @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.  
> **username_1**: 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)  
> **username_4**: @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.  
> **username_5**: 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.)  
> **username_1**: @Neel, I don't have an answer, but I wonder if this might merit a question of its own.  
> **username_5**: @Suresh: good idea. :)  

---

### Answer by username_2 on 2011-04-13. Score: 16

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...!


---

