Computer Science/Discrete Mathematics Seminar I

Counting connected components and Betti numbers was a known technique in algebraic complexity theory in the late 1970's and early 1980's. Speculation arose as to whether such methods could attack lower bounds in Boolean complexity theory (e.g., P vs. NP). This approach via cohomology (or, in particular, Betti numbers) is appealing due to a vast array of tools developed to study cohomology and its interplay with combinatorics. To our knowledge no essential progress has been made in this approach to date. We shall show that if one generalizes the setting to Grothendieck topologies and uses the machinery of the Grothendieck school (actually a very small part of this machinery), it is possible to circumvent two obstacles to connecting Boolean depth complexity lower bounds to cohomology. We describe ongoing research to look for models of Grothendieck topologies that yield, via these techniques, interesting lower bounds.