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.