Boolean Circuit Complexity Fall Semester, 1994-5

Lecture 7: December 8

Lecturer: Uri Zwick Scribe: Tal Yadid

7.1 Probabilistic Circuits

A probabilistic circuit is one which has, in addition to its standard inputs x_{1}, x_{2}, …, x_{n}, some specially designated inputs y_{1}, y_{2}, …, y_{m} called random inputs. When these random inputs are chosen from a uniform distribution, the output of the circuit is a random variable.

A probabalistic circuit with standard inputs x_{1}, x_{2}, …, x_{n} computes f(x_{1}, x_{2}, …, x_{n}) if P r[C(α_{1}, α_{2}, …, α_{n}) = f(α_{1}, α_{2}, …, α_{n})] ≥ \frac{3}{4} for each (α_{1}, α_{2}, …, α_{n}) ∈ \{0, 1\}^{n}.

Theorem 7.1 (Adleman,1977) If a function f(x_{1}, x_{2}, …, x_{n}) can be computed by a probabalistic circuit of size C(n), then it may be computed by a deterministic circuit of size O(nC(n)).

Proof: Let C be a probabalistic circuit that computes f(x_{1}, x_{2}, …, x_{n}). We define C_{k} as the circuit generated from C by duplicating it k times, and computing the majority of its outputs. Using that those outputs are binomially distributed with p ≥ \frac{3}{4}, we get (Chernoff): P r[C_{k}(α_{1}, α_{2}, …, α_{n}) ≠ f(α_{1}, α_{2}, …, α_{n})] ≤ e^{− \frac{k}{24}} for each (α_{1}, α_{2}, …, α_{n}) ∈ \{0, 1\}^{n}. Therefore, for k = 24n there exists a setting of the random inputs, which always gives the correct answer.

7.2 Lower Bounds for Monotone Circuits

A monotone circuit is a circuit over M_{2} = {∨, ∧}. A Boolean function f is called monotone if x ≤ y implies that f(x) ≤ f(y). The only functions computable by monotone circuits are monotone functions, and any monotone function can be computed by monotone circuits. The monotone circuit complexity of a monotone function f, denoted C_{M_{2}}(f), is the size of the smallest monotone circuit computing it. An example for a monotone function is the clique function from graph-theory. The clique function, denoted CLIQUE_{k,n} has (_{2}^{n}) variables, one for each potential edge in a graph on n edges. CLIQUE_{k,n} outputs 1 if and only if the associated graph contains a clique on some k vertices. A clique over specific k vertices can be computed with (_{2}^{k}) − 1 AND gates. Therefore, C_{M_{2}}(CLIQUE_{k,n}) = O((_{2}^{k})(_{k}^{n})) = O(n^{k}).

Strong lower bounds are known for monotone circuits. In 1985, Razbarov obtained a superpolynomial lower bound of size n^{Ω(log n)} for the monotone circuit complexity of some clique functions. In the same year, Andreev, using similar methods, proved an exponontial lower bound for a problem in NP. In 1987, Alon and Boppana improved Razborov’s lower bound, by using stronger combinatorial arguments. They proved a lower bound for CLIQUE_{k,n}

(where k = (\frac{n}{log n})^{\frac{2}{3}} ) of size e^{Ω(( \frac{n}{log n})^{\frac{1}{3}} )}.

Theorem 7.2 (Alon,Boppana 1987) C_{M_{2}}(CLIQUE_{k,n}) = e^{Ω(\sqrt{k})} for k = O((\frac{n}{log n})^{\frac{2}{3}} ).

We will prove the theorem for k = O((\frac{n}{log^{2} n})^{\frac{1}{3}} ), so the best lower bound we will get will

be e^{Ω(( \frac{n}{log^{2} n})^{\frac{1}{6}} )}. We will also look at the case of k = 3, and prove that C_{M_{2}}(CLIQUE_{3,n}) = Ω(\frac{n^{3}}{log^{4} n}), which is almost tight, since C_{M_{2}}(CLIQUE_{3,n}) = O(n^{3}) as we showed earlier. Note that using fast matrix multiplication, for any complete basis Ω, C_{Ω}(CLIQUE_{3,n}) = O(n^{2.376}). Tardos showed in 1988 an exponential gap between monotone circuits and general ones, for a certain monotone problem in P.

7.2.1 The Method of Approximation

Rozborov’s Method for proving lower bounds, shows that the behavior of small monotone circuits is constrained. To compare the behavior of the circuit with the behavior of the clique function, we will use the following input setting:

• A positive test graph - A graph on n vertices that consists of a clique on some set of k vertices and no other edges. These graphs are called positive because CLIQUE_{k,n} outputs 1 on them. Observe that there are (_{k}^{n}) such graphs, and they are the minimal graphs that CLIQUE_{k,n} outputs 1 on.

• A negative test graph - A graph formed by assigning each vertex a color from the set {1, 2, …, k − 1} and then putting edges between each pair of vertices with different colors. These graphs are called negative because CLIQUE_{k,n} outputs 0 on them. There are (k−1)^{n} possible coloring, and although different coloring can lead to the same graph, graphs formed from different coloring will be considered different, for counting purposes. These are the maximal graphs that CLIQUE_{k,n} outputs 0 on.

For a subset X of vertices, set the clique indicator of X, written ⌈X⌉ to be the the function of (_{2}^{n}) variables that is 1 if the associated graph contains a clique over the vertices X, and 0 otherwise. An approximator circuit is 0, 1, or an OR of at most m clique indicators, each on a set of cardinality at most l, where m = (p − 1)^{l}l!, l ≥ 2 and p ≥ 2 are parameters that depend on n and k that will be chosen later.

We have two goals:

• goal 1 Prove that CLIQUE_{k,n} cannot be well approximated by an approximator circuit.

• goal 2 Show that given good approximations to a gate inputs, we can obtain a good approximation for its output.

Combining those results, we will conclude that in order to output such a bad approximation, given good local approximations, the circuit that computes CLIQUE_{k,n} must consist of many gates.

In order to reach our goals, we introduce a combinatorial object, called sunflower:

7.2.2 Sunflowers

A sunflower is a collection of distinct sets Z_{1}, Z_{2}, …, Z_{p} called petals , such that the intersection Z_{i} ∩ Z_{j} is the same for every pair of distinct indices i and j. The common part Z_{i} ∩ Z_{j} is called the center of the sunflower.

Lemma 7.3 (Erdos,Rado 1962) Let Z be a collection of sets each of cardinality at most l. If |Z| > (p − 1)^{l}l! , then the collection contains a sunflower with p petals.

Proof: By induction on l. The case l = 1 is obvious: we have at least p distinct sets each of cardinality ≤ 1. These sets form a sunflower, with an empty center. For l ≥ 2, let M be a maximal subcollection of disjoint sets in Z, and let S be the union of the sets in M. If |M| ≥ p, then M itself forms a sunflower. Otherwise we have |S| ≤ (p−1)l. Since M is maximally disjoint, S intersects every set in Z. Therefore, some element i in S intersects more than (p − 1)^{l−1}(l − 1)! distinct sets in Z. Consider the following collection of sets of cardinality at most l − 1: Z′ = {X − {i} : i ∈ X and X ∈ Z}. From the choice of i we have: |Z′| > (p − 1)^{(l−1)}(l − 1)!. Thus, by induction, the collection Z contains a sunflower with p petals. Adding i back to all those petals gives the desired sunflower in Z.

7.2.3 Approximating OR and AND gates

Constructing approximator circuits by induction: An input variable x_{i,j} is equivalent to the clique indicator ⌈{i, j}⌉. Hence an input variable is already an approximator. Now suppose that the inputs of a certain gate have already been approximated, and suppose that C_{1} = ∨_{X∈A}⌈X⌉ and C_{2} = ∨_{X∈B}⌈X⌉, where |A| ≤ m and |B| ≤ m, are the approximators of the gate inputs.

• OR gate an approximate ∨ is denoted by ⊔ A natural way is : C_{1} ⊔C_{2} = C_{1} ∨C_{2} = ∨_{X∈A∪B}⌈X⌉ but |A ∪ B| can be as large as 2m. According to lemma 7.3, if |A ∪ B| > m then p of these vertex sets form a sunflower. In order to reduce the number of clique indicators, we replace these p sets with their center. This operation is called plucking procedure. Since the number of vertex sets decreases with each plucking, at most \frac{m}{p−1} pluckings will occur. The clique indicators of the remaining sets are then ORed together to form the approximate OR.

• AND gate an approximate ∧ is denoted by ⊓ A natural way : C_{1} ⊓ C_{2} = C_{1} ∧ C_{2} = ∨_{X∈A} ∨_{Y ∈B} (⌈X⌉ ∧ ⌈Y ⌉). But, the term ⌈X⌉ ∧ ⌈Y ⌉ is not a clique indicator, and there can be as many as m^{2} terms. To overcome this, first we replace the term ⌈X⌉ ∧ ⌈Y ⌉ by the clique indicator ⌈X ∪ Y ⌉. Then, we erase those clique indicators ⌈X ∪ Y ⌉ for which the |X ∪ Y | > l. Finally, we apply plucking procedure to the remaining clique indicators. There will be at most m^{2} pluckings. These steps guarantee that a valid approximator is formed.

Now that we know how to form an approximator to all the gates in a monotone circuit, we prove Theorem 7.2, first for k = 3. We choose l = 2. Notice that a clique indicator is now simply an edge indicator, also, the approximator of an AND gate in a monotone circuit computing CLIQUE_{3,n} has the form ∨_{{i,j}∈A∩B}x_{i,j}.

Claim 7.4 Every approximator is either identically 0 or outputs 1 on at least half of the negative test graphs.

Proof: Let A = ∨_{i=1}^{m′}⌈X_{i}⌉, 1 ≤ m′ ≤ m be an approximator which is not identically 0, then A ≤ ⌈X_{1}⌉ = x_{i,j}. The probability that both i and j were assigned different colors is exactly \frac{1}{2}.

Claim 7.5 The inequality C_{1} ∨ C_{2} ≤ C_{1} ⊔ C_{2} always holds. The inequality C_{1} ∧ C_{2} ≤ C_{1} ⊓ C_{2} fails on at most m^{2} positive test graphs.

Proof: C_{1} ⊔ C_{2} is obtained from C_{1} ∨ C_{2} by the plucking procedure. Each plucking can only enlarge the class of accepted graphs. If at least one of C_{1} and C_{2} is a constant, then C_{1} ∧ C_{2} = C_{1} ⊓ C_{2} holds. Otherwise, let C_{1} = ∨_{{i,j}∈A}x_{i,j} and C_{2} = ∨_{{i,j}∈B}x_{i,j}. We want to count positive test graphs for which C_{1} ∧ C_{2} = 1 but ∨_{{i,j}∈A∩B}x_{i,j} = 0. This means that the graph has an edge in A, another edge in B, but none in A ∩ B. Since our positive test graphs are triangles, a pair of edges can participate in at most one positive test graph, so the total number of such positibe test graphs is at most |A| · |B| ≤ m^{2}.