Take the 2-minute tour ×
Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It's 100% free, no registration required.

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?

share|improve this question
4  
I'm very curious to see the answer to this. Of course, the easiest would be to email Joel Friedman :) –  Suresh Venkat Apr 6 '11 at 2:36
add comment

2 Answers 2

up vote 27 down vote accepted

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.

share|improve this answer
4  
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 Apr 6 '11 at 15:53
2  
@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 Apr 6 '11 at 17:23
    
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 Apr 7 '11 at 2:27
1  
@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 Apr 8 '11 at 14:24
1  
@Neel, I don't have an answer, but I wonder if this might merit a question of its own. –  Suresh Venkat Apr 13 '11 at 15:48
show 2 more comments

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

share|improve this answer
4  
Welcome to CStheory.SE! –  Hsien-Chih Chang 張顯之 Apr 13 '11 at 15:06
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.