7
$\begingroup$

In this question, I learned that complexity theorists had considered using Grothendieck topologies to model Boolean circuits. This has not, apparently, led to any new lower bounds yet, but I'm not so interested in lower bounds, and 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 (roughly speaking) to model splitting and pasting the branches of if-statements together as coverings of programs. It's very interesting seeing a related idea arise in complexity theory! However, in this (and the followup work Balat and di Cosmo did with Fiore), they didn't need any serious machinery of algebraic topology, since they were more focused on decidability than efficiency.

However, binary decision diagrams (BDDs) (sort of the restriction of this problem to first-order) are extremely focused on efficiency, and I'm curious whether whether the cohomological approach nicely models any of the heuristics people use when building BDD libraries?

Improve this question
$\endgroup$
1
  • 3
    $\begingroup$ I'm almost certain nobody has looked at this question specifically, but you're better off asking Joel Friedman directly than posting here. Alternatively, Friedman has just recently posted a new preprint to the ArXiv that shows how several graph-theoretic concepts fit into his Grothendieck-topology framework, so you could try reading his paper and figuring out the answer to your question yourself. arxiv.org/abs/1104.2665 $\endgroup$
    – Timothy Chow
    Commented Apr 15, 2011 at 14:18

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.