Cohomological approach to boolean complexity

Question

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?

Answer 1

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.

Answer 2

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