Cohomology in Grothendieck Topologies and Lower Bounds in Boolean Complexity

COMPUTER SCIENCE/DISCRETE MATH I
Topic:Cohomology in Grothendieck Topologies and Lower Bounds in Boolean Complexity
Speaker:Joel Friedman
Affiliation:University of British Columbia
Date:Monday, February 13
Time/Room:11:15am - 12:15pm/S-101

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.