Figure 2. an illustration of the statement of Lemma 3 (a), and Lemma 4 (b). note that when the low degree polynomial f does disagree with F we have no good guarantee on the error. this means that f may be a good approximant almost everywhere but not on average.

(a)

f

1

0

F

(b)

Eν

1

f ≈ F =G1∧G2∧...∧Gk

Figure 3. an illustration of the inductive step where an approximating polynomial f is constructed from the approximating polynomials g1, g2, . . . , gk.

AND

G1 ≈g1

G2 ≈g2

G1 ≈gk

thus cannot give an explicit construction for f. Instead, we will construct a distribution on polynomials f that succeeds with high probability on any given input. Thus the distribution is expected to have a low error with respect to ν, which implies that there is a specific f that has a small error with respect to ν.

We will show how to make a step when the output gate in f is an AND gate (see Figure 3). Since the whole construction is symmetric with respect to 0 and 1, the step also holds for an OR gate. Let

0

according to ν of the region of disagreement between f and F is small.

Lemma 3 (or its slight variation) has been proved by Razborov11 and Smolensky13 in the late 1980s. The tools for the proof of the lemma have been developed in Valiant and Vazirani. 14 Razborov and Smolensky used the lemma to give stronger lower bounds on bounded depth circuits. Let Ac0[ p] ⊃ Ac0 be the class of functions computable using a bounded-depth circuit that in addition to the AND and OR gates is allowed to use the MODp gate: the gate outputs 1 if and only if the number of 1’s among its inputs is divisible by p. We already know that PARITY Ï Ac0, and thus Ac0[ 2]  Ac0. Razborov and Smolensky showed that the MODp function cannot be computed efficiently by an Ac0[q] circuit where q ¹ p. In particular, this means that PARITY Ï Ac0[ 3].

The proof of Lemma 3 is combinatorial, and is much simpler than the proof of Lemma 2. In fact, we will be able to present its entire proof below. To obtain the results in Section 5 we will need a slight strengthening of the lemma.

F = G1 ∧ G2 ∧ . . . ∧ Gk ,

where k < m. For convenience, let us assume that k = 2 is a power of 2. We take a collection of

t := s log m

Lemma 4. Let ν be any probability distribution on {0, 1}n. For a circuit of depth d and size m computing a function F, for any s, there is a degree r = (s · log m)d polynomial f and a boolean function Eν computable by a circuit of depth £ d + 3 and size O(m2r) such that

random subsets of { 1, 2,..., k} where each element is
included with probability p independently of the others: at
least s subsets for each of the p = 2− 1, 2− 2, . . . , 2− = 1/k. Denote
the sets by S1, . . . , St—we ignore empty sets. In addition, we
make sure to include { 1, . . . , k} as one of the sets. Let g1, . . . ,
gk be the approximating polynomials for G1,. .. , Gk that are
guaranteed by the induction hypothesis applied to G1, . . . , Gk
with depth d − 1. We set
• Pν [Eν(x) = 1] < 0.82sm, and

Thus, not only does the polynomial from Lemma 3 exist, but there is a simple Ac0 “error circuit” Eν that given an input can tell us whether f will make an error on the input. The function Eν is shown on Figure 2(b).

We will now prove Lemma 4. A curious property of the construction is that it gives a probabilistic algorithm for producing the low degree polynomial f that approximates F almost everywhere.

Proof. (of Lemma 4) We construct the polynomial f by induction on the depth d of F, and show that with high probability f = F. The function Eν follows from the construction. Note that we do not know anything about the measure ν and

By the induction assumption, the degrees of gj are degg £
(s . log m)d − 1, hence the degree of f is bounded by degf £ t .
degg £ (s . log m)d. Next we bound the error P[ f ¹ F ]. It consists
of two terms:
( 6)

In other words, to make a mistake, either one of the inputs to the final AND gate has to be wrong, or the approximating function for the AND has to make a mistake. We will focus on the second term. The first term is bounded by union bound. We fix a vector of specific values G1(x),. .. , Gk(x), and calculate the probability of an error over the possible choices of the random sets Si.