CS 298-2
Theory Seminar
Joel Friedman
University of British Columbia
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.