Boolean Circuit Complexity Fall Semester, 1994-5

Lecture 11: January 05

Lecturer: Uri Zwick Scribe: Hana Kvartin

11.1 The class AC^{0}

Definition We define AC^{0} as class of functions for which exists a circuit U_{∞} of finite depth and polynomial size.

We will make a few assumptions :

• If we have a circuit, we can convert it to a formula by duplicating all the entries that we use more then once. It enlarges the size of circuit at most in polynomial order. Therefore we can assume, that we will deal with formulas only.

• The circuit is made of layers, because if it doesn’t, we can add the OR or AND gate in the middle (i.e., exchange x with x ∨ x, for example ).

• The layers are consistent and alternating ( i.e., the first layer consists of OR’s, the second of AND’s etc. )

It is easy to see, that AC^{0} ⊆ NC^{1}, where NC^{1} represents the circuits with fan-in 2 and logarithmic depth. AC^{0} has polynomial number of gates, so each gate has a polynomial number of inputs, and we can represent each gate in an AC^{0} circuit as a small tree.

We will show : AC^{0} ≠ NC^{1}, and this because XOR_{n} ∉ AC^{0} ( This also implies, that MAJ_{n} ∉ AC^{0} ) .

How many gates do we need to calculate XOR_{n} in depth 2 ? The circuit with depth 2 for calculating XOR_{n} is exactly DNF or CNF, so it consists of 2^{n+1} + 1 gates.

How many gates do we need to calculate XOR_{n} in depth 3 ? We can divide n bits to \sqrt{n} subsets of size \sqrt{n} . Then we can calculate XOR of each subset, and then XOR of XOR’s. It seems that we need 4 layers, but we can amalgamate two of them if we represent XOR of each subset as CNF and XOR of XOR’s as DNF. So we get \sqrt{n}2^{\sqrt{n}} + 2^{\sqrt{n}} gates.

Theorem 11.1 For each constant d there exist U_{∞} circuits of depth d and size O(n^{\frac{d−2}{d−1}} 2^{n^{\frac{1}{d−1}}} ) for calculating XOR_{n}.

We will obtain lower bounds, that come very close to this upper bound.

Theorem 11.2 Every U_{∞} circuit of depth d for calculating XOR_{n} contains 2^{Ω(n^{\frac{1}{d−1}} )} gates.

The lower bounds on the size of depth of circuits for parity were obtained by many researches :

’83 - Ajtai - n^{Ω(log n)}

’83 - Furst, Saxe, Sipser - n^{Ω(log n)}

’85 - Yao - 2^{Ω(n^{\frac{1}{d−1}} )}

’86 - Håstad - 2^{Ω(n^{\frac{1}{d−1}} )} - Switching Lemma.

Switching Lemma : Given a circuit of depth d observe every pair of layers “AND of OR’s”. If we can change every second pair to OR of AND’s, we will be able to union two layers. The problem is that this switching procedure can require exponential size. So the idea is to use random dispositions to part of variables in the way that we still will calculate XOR large enough but not too large.

’87 - Razborov, Smolensky - 2^{n^{Ω(1/d)}} and this by using the approximation of Boolean functions by polynomials of small degree over GF(3).

’91 - Aspnes, Beigel, First, Rudich - 2^{n^{Ω(1/d)}} by using polynomials over ℤ.

In this course we present the last two proofs, as they are somewhat simpler than Håstad’s proof using the Switching Lemma.

11.1.1 The representation of Boolean functions as polynomials over ℤ

Claim 11.3 Every boolean function f : {0, 1}^{n} ⟶ {0, 1} can be represented (explicitly) by a multi-linear polynomial in variables x_{1}, x_{2}, ..., x_{n}.

The class AC^{0} 3

Proof: f can be represented by the polynomial P = ∑_{α:f(α)=1} ∏_{i=1}^{n} x_{i}^{α} where x_{i}^{α} = x_{i} if α = 1 and x_{i}^{α} = 1 − x_{i} if α = 0 . For every (x_{1}, ..., x_{n}) ∈ {0, 1}^{n} we have p = f. The representation is unique because the set of monomials ∏_{i∈S} x_{i} for S⊆{1, 2, ..., n} is linearly independent over {0, 1}^{n}.

Examples: AND_{n} = ∏_{i=1}^{n} x_{i} OR_{n} = 1 − ∏_{i=1}^{n}(1 − x_{i}) XOR_{n} = ^{\frac{1−∏_{i=1}^{n}(1−2x_{i})}{2}}

Let us look now at Boolean function as function from {−1, 1}^{n} to {−1, 1}, where 0↔1, and 1↔ − 1. In this representation XOR_{n} = ∏_{i=1}^{n} x_{i} .

Definition The sign function sgn(x) is defined as follows : sgn(x) = 1 if x > 0 sgn(x) = 0 if x = 0 sgn(x) = −1 if x < 0 .

We present two additional ways in which polynoms can represent Boolean functions.

Definition We will say that p strongly represents f if and only if for each x∈{0, 1}^{n} we have f(x) = sgn(p(x))

Definition We will say that p weakly represents f if and only if p≢0,for each x∈{0, 1}^{n}, if p(x)≠0 then f(x) = sgn(p(x))

Definition We will say that p approximates f with e mistakes if and only if f(x) ≠ sqn(p(x)) for at most e x’s.

Definition The strong degree of f, denoted d_{s}(f) is the minimum degree of the polynom that strongly represents f.

Definition The weak degree of f, denoted d_{s}(f) is the minimum degree of the polynom that weakly represents f.

Lemma 11.4 d_{w}(XOR_{n}) = n .

Proof: For S ⊆ [n] = {1, 2, ..., n}, let ϕ_{s} be ∏_{i∈S} x_{i}. It is clear that XOR_{n} = ϕ_{{1,2,...,n}} = ψ. Let us define the internal product of functions f, g as < f, g >= ∑_{x∈{−1,1}^{n}} f(x)g(x). If S_{1}, S_{2} ⊆ [n] then ϕ_{S_{1}}.ϕ_{S_{2}} = ϕ_{S_{1}⊕S_{2}} when S_{1}⊕S_{2} = (S_{1}∪S_{2})\(S_{1}∩S_{2}), because if x_{i} ∈ {−1, 1}, then x_{i}^{2} = 1. Therefore if S_{1} ≠ S_{2} then < ϕ_{S_{1}}, ϕ_{S_{2}} >= ∑_{x} ϕ_{S_{1}⊕S_{2}}(x) = 0. Let p be polynom that weakly represents XOR_{n}. We will get < p, ψ >> 0. If deg(p) < n then < p, ψ >= 0, and this is a contradiction.

Lemma 11.5 If S ⊆ \{−1, 1\}^{n} and |S| < ∑_{i=0}^{k} \binom{n}{i} then there exists a polynom q ≠ 0 that it’s degree ≤ 2k so that q(x) ≥ 0 for all x and g(x) = 0 for all x ∈ S.

Proof: We first construct a polynom r ≠ 0 of degree ≤ k. We then take q = r^{2}. A polynom of degree k has ∑_{i=0}^{k} \binom{n}{i} coefficients. Each constraint r(x) = 0 for specific x ∈ S is a linear homogeneous equation on these coefficients. We’ll get a homogeneous system of linear equations in which the number of equations is less than the number of variables. The system therefore has a nontrivial solution.

Lemma 11.6 Let p(x_{1}, x_{2}, ..., x_{n}) be polynom of degree k, and let f(x_{1}, x_{2}, ..., x_{n}) be a Boolean function such that p approximates f, k < d_{w}(f). S = {x : f(x) ≠ sgn(x)}. Then,

|S| ≥ ∑_{i=0}^{⌊ \frac{dw(f)−k−1}{2} ⌋} \binom{n}{i}

Proof: If S is smaller than the above bound, then according to the previous lemma there exists a polynom q ≠ 0 with degree at most d_{w}(f) − k − 1 such that q(x) ≥ 0 for all x and q(x) = 0 for x ∈ S. The polynom pq weakly represents f but its degree is less that d_{w}(f), which is a contradiction.

Theorem 11.7 If p(x_{1}, x_{2}, ..., x_{n}) approximates XOR_{n} with at most 0.158 · 2^{n} errors, then its degree is at least \sqrt{n}.

Proof: Let p be a polynom of degree smaller than \sqrt{n}. Then according to the previous lemma,

|S| ≥ ∑_{i=0}^{⌊ \frac{n−\sqrt{n}−1}{2} ⌋} \binom{n}{i} > 0.158 · 2^{n}

Let us show now that we can approximate the output of every small U_{∞}-circuit by a polynom of low degree. (This is similar to what we did with monotone circuits ). We have to show how to approximate the AND’s and OR’s, using low degree polynomials.

Lemma 11.8 For every ϵ > 0 and every probability distribution on {0, 1}^{n}, there exists a polynom of degree O(log \frac{1}{ϵ} log n) that approximates ⋁_{i=1}^{n} x_{i} with probability of error of at most ϵ ( when the input vector is drawn according to the given distribution on {0, 1}^{n}.

Proof: Define S_{0} = [n]. The set S_{i} will be obtained from S_{i−1} by deleting each element with probability \frac{1}{2}. For each set S_{i}, for1 ≤ i ≤ log n + 1 we define a polynom p_{i} = ∑_{j∈S_{i}} x_{j} and then we define the polynom P = 1 − ∏_{i=0}^{log n+1}(1 − p_{i}) . Note, that P is the OR of the polynomials P_{1}, .., P_{log(n+1)}. If x_{i} = 0, for 1 ≤ i ≤ n then P = 0. If there exists i such that p_{i} = 1 then P = 1. We have to find, therefore, the probability that there will be i for which p_{i} = 1. There can be three cases:

• p_{log n+1} > 1

• p_{0} = 1 • p_{0} > 1, p_{log n+1} ≤ 1, i.e. there exists i for which p_{i} > 1, but p_{i+1} < 1.

The probability of case 1 is at most n(\frac{1}{2})^{log n+1} = \frac{1}{2}. Case 1 is bad. Case 2 is good. What is the probability in case 3 that p_{i+1} = 1 ? P r(p_{i+1} = 1|p_{i+1} ≤ 1) =? P r(p_{i+1} = 0) = 2^{−p_{i}} P r(p_{i+1} = 1) = p_{i}2^{−p_{i}}, and that is because we want to leave exactly one element from of

p_{i}.

P r(p_{i+1} = 1|p_{i+1} ≤ 1) = \frac{p_{i}}{p_{i+1}} ≥ \frac{2}{3} Therefore the probability that there will be 0 ≤ i ≤ log n + 1 for which p_{i} = 1 is at least

\frac{1}{2} ∗ \frac{2}{3} = \frac{1}{3}. We can improve the probability by repeating the same experiment O(log \frac{1}{ϵ}) times and

define P = 1 − ∏_{k=1}^{O(log( \frac{1}{ϵ}))} ∏_{i=0}^{log(n+1)}(1 − p_{i}^{(k)}) where p_{i}^{(k)} is the i-th polynomial obtained in the i-th experiment.

For every specific input x ∈ {0, 1}^{n} the probability that P will return the right answer is at least 1 − ϵ. Therefore for every distribution on the inputs the probability that P will be wrong is ≤ ϵ. Therefore exists a specific polynom P that the probability that it will be wrong on an input chosen according to the given distribution is ≤ ϵ.

That was the proof for the approximated OR. The proof for the approximated AND is similar, using the de Morgan rules.