TIME: 3:00-4:00 pm,  April 19, 2006

PLACE: CSE 503

TITLE: Cohomology in Grothendieck Topologies and Lower Bounds in Boolean Complexity

SPEAKER:  Joel Friedman
          UBC

ABSTRACT:
Cohomology, in particular counting 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), by
modeling Boolean functions with topological objects.

We shall show that if one generalizes the setting to Grothendieck
topologies, it may be 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.
As a simple example, we show that if we consider circuits with only
AND gates, which is essentially a SET COVER problem, using a free
category and injectives sheaves (i.e., an extremely special and simple
situation) we can rederive the relaxed LP bound.

For the talk we do not assume prior knowledge of complexity theory or
Grothendieck topologies.