Cohomology in Grothendieck Topologies and Lower Bounds in Boolean Complexity

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.

Speaker Details

AB Harvard College 1984, PhD University of California, Berkeley 1987, Assistant Prof, Princeton University, Computer Science 1987-1993 (two semesters on leave at Hebrew University, Computer Science) currently Professor at University of British Columbia, since then Department of Computer Science and Department of Mathematics.

Date:
Speakers:
Joel Friedman
Affiliation:
University of British Columbia
    • Portrait of Jeff Running

      Jeff Running