Cohomology in Grothendieck Topologies and Lower Bounds in Boolean Complexity II: A

Simple Example^{∗}

Joel Friedman^{†}

March 31, 2006

Abstract

In a previous paper we have suggested a number of ideas to attack circuit size complexity with cohomology. As a simple example, we take circuits that can only compute the AND of two inputs, which essentially reduces to SET COVER. We show a very special case of the cohomological approach (one particular free category, using injective and superskyscraper sheaves) gives the linear programming bound coming from the relaxation of the standard integer programming reformulation of SET COVER.

1 Introduction

In [Fri05] we introduced several techniques that may prove useful in using cohomology (on Grothendieck topologies) for obtaining lower bounds on circuit complexity. In this paper we simplify this problem to complexity involving only conjunctions of Boolean functions. We then show that a simple example of a Grothendieck topology, sheaves, and open sets lead to the “linear programming” bound. Furthermore we improve a bound in [Fri05].

∗MSC 2000 classifications: primary: 68Q17, secondary: 14F20, 18G99 †Departments of Computer Science, University of British Columbia, Vancouver, BC V6T 1Z4, CANADA, and Departments of Mathematics, University of British Columbia, Vancouver, BC V6T 1Z2, CANADA. jf@cs.ubc.ca, http://www.math.ubc.ca/~jf. Research supported in part by an NSERC grant.

Let S be a set, and denote by 𝔹^{S} = {0, 1}^{S} the collection of functions from S to 𝔹 = {0, 1} (viewing 1 as TRUE and 0 as FALSE). By a formal AND measure we mean a function, h, from 𝔹^{S} to the non-negative reals such that for all f, g ∈ 𝔹^{S} we have

h(f ∧ g) ≤ h(f) + h(g)

(compare the notion of a formal complexity measure, e.g., see [Weg87]). Given a subset S_{1} = {f_{1}, …, f_{r}}, let size(f) be the minimum number of elements of S_{1} whose conjunction is f; we define size(f) to be infinite if f cannot be expressed as such a conjuction. Equivalently size(f) is the size of the smallest formula computing f via conjunctions of elements of S_{1}. By induction on “size” we see that for any formal AND measure, h, we have

size(f) ≥ h(f)/M, where M = max_{i} h(f_{i}).

If h also satisfies

h(f) = h(¬f),

then similarly we have an h(f)/M lower bound on the size of a formula as before, but where the operations are either conjunctions or the negation of a conjuction; then log_{2}(h(f)/M) would bound the formula (or circuit) depth.

Given S and f_{1}, …, f_{r}, determining size(f) is NP-complete. It can be approximated (to within O(log r)) by a linear program. We shall show that the “virtual zero extensions” described in [Fri05], just in the special case of a free category with sheaves with no non-trivial higher cohomology, give this linear programming bound (or more precisely its dual). We finish by recalling the notion of virtual zero extensions.

We sketch the ideas, referring to [Fri05] for the details. Let C be a finite category, and endow it with the grossière topology (meaning that a sheaf is the same thing as a presheaf). Let F, G sheaves of finite dimensional ℚvector spaces on C, and let U be an open set of C (i.e., a sieve), and Z be a closed set. We say that a sheaf, H, is a virtual G_{U,Z} if there is an exact sequence,

0 → G_{U} → G_{U∩Z} ⊕ H → G_{Z} → 0,

where the maps G_{U} → G_{U∩Z} and G_{U∩Z} → G_{Z} are the usual maps (i.e., the identity on the intersection of the supports), and where G_{A} denotes G restricted to A and extended by zero outside A. See [Fri05] for conditions on the existence of H; for a free category (see [Fri05]) H always exists. The following theorem is an improvement over the bound in [Fri05].

Theorem 1.1 In the situation above, with H a virtual G_{U,Z}, we have

cc(F, G_{U∩\overline{Z}}) ≤ cc(F, G) + cc(F, G_{U}) + cc(F, G\overline{Z}),

where cc(A, B) is the sum of the dimensions of Ext_{C}^{i}(A, B) over all nonnegative i, and \overline{Z} is the complement of Z.

We shall prove this theorem in Section 3. Now assume that we have a map f ↦ U_{f} from 𝔹^{S} to open sets of C such that U_{f∧g} = U_{f} ∩ U_{g}. Then

h(f) = cc(F, G_{U_{f}})

is a formal AND measure, provided that cc(F, G) = 0.

The idea to test the ideas of [Fri05] on AND’s alone arose in conversations with Les Valiant. We wish to thank him, as well as Janos Simon, for discussions.

2 AND complexity

Given S and S_{1} ⊂ 𝔹^{S}, determining size(f) is NP-complete, as it is almost a reformulation of SET COVER (see [Vaz01], for example, for SET COVER); indeed, to determine how many S_{1} elements we need to obtain f, we may assume f ≤ f_{i} for all i, and then the question is how many f_{i}^{−1}(0) are required to cover f^{−1}(0). The point of this paper is to show that the dual of the usual “linear programming” lower bound on size/depth complexity arises as a very special (and degenerate) case of the sheaf bound. Specifically, the size complexity is given by the integer program

min ∑_{i∈R} μ_{i}, subject to
∑_{i∈R} μ_{i}(1 − f_{i}(s)) ≥ 1, ∀s ∈ f^{−1}(0)
μ_{i} = 0, 1 i ∈ R,

where R is the set of i with f ≤ f_{i}. A lower bound to this program is given by the “relaxed” linear program where the μ_{i} are non-negative reals. The gap between the integer and linear program is known to be as high as O(log r) in certain cases, and never higher (see [Vaz01]). Equivalent to the linear program is its dual,

max ∑_{s∈f^{−1}(0)} α_{s}, subject to
∑_{s∈f^{−1}(0)} α_{s}(1 − f_{i}(s)) ≤ 1, ∀i ∈ R
α_{s} ≥ 0 ∀s ∈ S

Say that s ∈ f^{−1}(0) demands f_{i} if f_{i}(s) = 0 and f_{j}(s) = 1 for j ≠ i. If for each i = 1, …, r there is an s_{i} that demands f_{i}, then we take α_{s} to be 1 or 0 according to whether or not s is one of the s_{i}, and then we see that the LP-bound is exact, i.e., gives the true size complexity (namely r).

For example, consider the case where S = {0, 1}^{n} and the size one functions are {0, 1, x_{1}, ¬x_{1}, …, ¬x_{n}}; given f, we discard 0, 1 and all size one functions not ≥ f; we see that either f is the conjunction of the functions leftover, and the LP-bound is exact, or f is of infinite size complexity, and the LP-bound is also infinite (the primal is infeasible, and for the dual there is an s with f(s) = 0 but f_{i}(s) = 1 for all leftover f_{i}; then α_{s} can be taken arbitrarily large).

3 Improved Inequality

In this section we prove Theorem 1.1.

The short exact sequence

0 → G_{U∩\overline{Z}} → G_{U} ⟶^{β} G_{U∩Z} → 0

gives a long exact sequence, yielding

dim(Ext^{i}(F, G_{U∩\overline{Z}})) = dim(Coker β^{i−1}) + dim(Ker β^{i}),  (1)

where β^{i}: Ext^{i}(F, G_{U}) → Ext^{i}(F, G_{U∩Z}) are the maps arising from β. It suffices to bound the right-hand-side of equation (1).

The virtual zero extension gives a short sequence

0 → G_{U} ⟶^{β⊕γ} G_{U∩Z} ⊕ H → G_{Z} → 0.

Letting γ^{i} be, as before, the map γ in Ext^{i}(F, · ) gives

dim(Ext^{i}(F, G_{Z})) = dim(Coker (β^{i} ⊕ γ^{i})) + dim(Ker (β^{i+1} ⊕ γ^{i+1})).

Since Coker β^{i} injects into Coker (β^{i} ⊕ γ^{i}), we have

∑ dim(Coker β^{i}) ≤ ∑ dim(Coker (β^{i} ⊕ γ^{i})) ≤ cc(F, G_{Z}).

And clearly

∑ dim(Ker β^{i}) ≤ ∑ dim(domain(β^{i})) = ∑ dim(Ext^{i}(F, G_{U})) = cc(F, G_{U}).

Summing in equation (1) yields

cc(F, G_{U∩\overline{Z}}) ≤ cc(F, G_{Z}) + cc(F, G_{U}).

We now finish the proof using

cc(F, G_{Z}) ≤ cc(F, G) + cc(F, G\overline{Z})

that follows from the exact sequence

0 → G\overline{Z} → G → G_{Z} → 0.
□

4 A Trivial Bound

In this section we use the notation of [Fri05]: if C is a category and P ∈ Ob (C), then k_{P} is the inclusion Δ_{0} → C where Δ_{0} is the category with one object, 0, and one morphism, and k_{P} (0) = P; also, if u: C → C′ is a functor, u^{∗} is the pullback and u_{∗} (respectively u_{!}) is its right (respectively left) adjoint (this notation comes [sga72], Exposé I, Section 5.1).

Lemma 4.1 Let C be the free category on the graph, G. For a closed inclusion i: Z → C, let Hom_{Z}(P, Q) be the set of all paths in G all of whose vertices except the last lie outside Z; in particular, if P ∈ Z, then Hom_{Z}(P, Q) is empty if Q ≠ P and consists of a single element (the zero length path about P) if Q = P. For any P ∈ Ob (C) we have that

i_{∗}i^{∗}k_{P ∗}ℚ ≃ ⨁_{Q∈Z}(k_{Q∗}ℚ)^{Hom_{Z}(P,Q)}.  (2)

Proof Let F_{L}, F_{R} denote the sheaves on the left- and right-hand-side of equation (2). First note that i_{∗}i^{∗} is simply restriction to Z followed by extension by 0, and F_{R} clearly vanishes outside Z. So it suffices to give anisomorphism F_{L}(X) ≃ F_{R}(X) for each X ∈ Z that is functorial in X.

We have that (k_{P ∗}ℚ)(X) is Hom(P, X) copies of ℚ, and Hom(P, X) is the number of paths in G from P to X. For each path in G from P to X, once a vertex in the path, Q, falls in Z, all subsequent vertices remain in Z. Hence we have a set theoretic bijection

b_{X}: ⋃_{Q} Hom_{Z}(P, Q) × Hom(Q, X) → Hom(P, X)

for each X. Furthermore this bijection is functorial in X, in that if ϕ: X_{1} → X_{2} is a morphism, then we have that ϕb_{X_{1}} = b_{X_{2}}ϕ, the second ϕ acting on each Hom(Q, X_{1}). This gives the desired functorial isomorphism F_{L}(X) ≃ F_{R}(X).

□

Now let S be a finite set, and let M_{S} be the graph whose vertices are the functions S → {0, 1} with one or zero edges from f to g according to whether or not f ≤ g and f(s) = g(s) for all but exactly one s ∈ S. Let C be the free graph on M_{S}. We call M_{S} the monotone S-cube, and C the S-path category. For f ∈ Ob (C), let U_{f} be the smallest open set containing f, i.e., the set of all objects no greater than f. By a subcube of C be mean a collection of objects whose values at a subset of S are fixed.

Consider the model, f ↦ (C, F, G_{U_{f}}), where G = k_{P ∗}ℚ and where F and P are to be specified later. Since C is free, virtual zero extensions always exist. If Z_{f} denotes the complement of U_{f}, we have

cc(f) = ∑_{Q∈Z_{f}}(dim F (Q)) |Hom_{Z_{f}} (P, Q)|.

Of course, the dim F (Q) can be arbitrary non-negative integers by taking F to be a sum of superskyscraper sheaves, i.e., a sheaf, F, where for each morphism ϕ ∈ C we have F ϕ is the zero morphism.

We claim this recovers the linear programming bound. Indeed, let P = 0, and let F vanish outside of the points δ_{s} where s ∈ S and δ_{s} is the Dirac delta function at s. Then cc(F, G) = 0, since F (0) = 0, and

cc(g) = ∑_{s} A_{s}(1 − g(s)),

where A_{s} is the dimension of F (δ_{s}). So we get

size(f) ≥ ∑_{s} A_{s}/M,

for any M with

∑_{s} A_{s}(1 − f_{i}(s)) ≤ M;

this is just the linear programming bound (restricted to α_{s} = A_{s}/M rational, α_{s} as in Section 2). Furthermore, it is not hard to see that varying G injective and F arbitrary and taking linear combinations we cannot get anything better than the linear programming bound. Indeed, since f = 0, we have cc(f) = 0 unless P = 0; so any P ≠ 0 terms can be discarded in an optimal bound. Similarly, if P = Q, then cc(F, G) is already 1 and cc(f) is no greater, so such terms can be discarded (since the bound size(f) ≥ 1 can always be achieved by the linear program). Finally, if P = 0 and Q ≠ 0 and Q ≠ δ_{S}, then

cc(f) = ∑_{(A,B)∈E_{S}} N_{P,Q}(A, B)cc_{A,B}(f),

where E_{S} are the edges of G_{S}, N_{P,Q}(A, B) is the number of paths from P to Q in G_{S} that pass through the edge (A, B), and cc_{A,B} denotes the cohomological complexity when P = A and F is zero outside B and ℚ on B. In the above displayed sum we may discard the A with A ≠ 0, as mentioned before, and we are left with a cohomological complexity as before.

The bound we get on size(f) can, of course, be derived without cohomology. Indeed, consider any formal function

h(f) = ∑_{ϕ∈Hom_{Z_{f}} (P, · )} A(ϕ),  (3)

where A is a any non-negative function. Then h is a formal AND measure, since Hom_{Z_{f∧g}} ⊂ Hom_{Z_{f}} ∪ Hom_{Z_{g}}.

We pause for a mild generalization of this notion. By a conjuctively closed family we mean an C ⊂ 𝔹^{S} such that f, g ∈ C implies f ∧ g ∈ C; by a conjunctively closed complement we mean the complement in 𝔹^{S} of a conjunctively closed family, or equivalently a B ⊂ 𝔹^{S} such that f ∧ g ∈ B implies at least one of f, g lies in B. For such a B, we have χ_{B}, the characteristic function of B is a formal AND measure, and therefore so is any non-negative linear combination of such characteristic functions; this is an essential generalization of the h in equation (3).

Let us mention that taking G = (k_{P ∗}ℚ)_{U} for an open set, U, yields such a bound; indeed, it is not hard to see that we get cc(f) as in equation (3) with A(ϕ) = β(tϕ) with

β(Q) = dim F (Q) + dim V (Q) − 2 rank(M),

where

V (Q) = ⨁_{χ∈Hom\overline{U} (Q, · )} F (tχ),

and M: V (Q) → F (Q) is the map whose χ component is F (χ); clearly β (and therefore A) is non-negative.

References

[Fri05] Joel Friedman. Cohomology of grothendieck topologies and lower bounds in boolean complex-

       ity.  2005.  http://www.math.ubc.ca/~jf, also
       http://arxiv.org/abs/cs/0512008, to appear.

[sga72] Théorie des topos et cohomologie étale des schémas. Tome 1: Théorie des topos. Springer-Verlag, Berlin, 1972. Séminaire de Géométrie Algébrique du Bois-Marie 1963–1964 (SGA 4), Dirigé par M. Artin, A. Grothendieck, et J. L. Verdier. Avec la collaboration de N. Bourbaki, P. Deligne et B. Saint-Donat, Lecture Notes in Mathematics, Vol. 269.

[Vaz01] Vijay V. Vazirani. Approximation algorithms. Springer-Verlag, Berlin, 2001.

[Weg87] Ingo Wegener. The complexity of Boolean functions. Wiley-Teubner Series in Computer Science. John Wiley & Sons Ltd., Chichester, 1987.