If all the Gj(x)’s are 1 then the value of F(x) = 1 is calculated correctly with probability 1.
Suppose that F(x) = 0 (and thus at least one of the Gj(x)’s
is 0). Let 1 £ z £ k be the number of zeros among G1(x), . . . ,
Gk(x), and a be such that 2a £ z < 2a+ 1. Our formula will work
correctly if one of the sets Si hits exactly one 0 among the
z zeros of G1(x), . . . , Gk(x). We will consider only the sets Si
above that are likely to hit exactly one zero. Specifically, let
S be a random set as above with p = 2− a − 1. The probability of
S hitting exactly one zero is exactly
Hence the probability of the formula being wrong after
s such sets is bounded by 0.82s. Since this is true for any
value of x, we can find a collection of sets Si such that the
probability of error as measured by ν is at most 0.82s. By
making the same probabilistic argument at every node and
applying the union bound, we get that the condition “if the
inputs are correct then the output is correct” is satisfied by
all nodes except with probability < 0.82sm. Thus the error of
the polynomial is < 0.82sm.
5. K-Wise inDePenDent DistRiButions
anD Lo W-DePth CiRCuits
Next we turn our attention to proving the main result,
Theorem 1. The result will give another way in which Ac0
circuits can be approximated using low-degree polynomials.
Theorem 1. r(m, d, ε)-independence ε-fools depth-d AC0
circuits of size m, where
appropriate approximation of F with low degree polynomials.
Bazzi2 has given the following equivalent characterization of
fooling through polynomial approximations using linear pro-
gramming duality:
Lemma 6. Let F: {0, 1}n → {0, 1} be a boolean function, k ≥ 0
an integer, and ε > 0. Then the following are equivalent:
2
1. Any k-wise independent distribution ε-fools F.
2. there exist a pair of “sandwiching polynomials” fl, fu:
{0, 1}n → R such that:
• low degree: deg ( fl ), deg ( fu) ≤ k;
• sandwiching: fl ≤ F ≤ fu on {0, 1}n;
• small error: E[F − fl ], E[ fu − F ] ≤ ε, where the expectation
is with respect to the uniform distribution on {0, 1}n.
The sandwiching polynomials are illustrated on Figure
4(a). Since part ( 1) in Lemma 6 is what we need to prove,
we will only be interested in the “( 2) ⇒ ( 1)” direction of
the theorem, which is the “easy” direction, and which we
can prove here. Suppose ( 2) holds, and let m be any k-wise
independent distribution. The polynomial fl is of degree £
k, which as observed in Section 2, implies that Em[ fl ] = E[ fl ].
Thus,
Em [F] ≥ Em [ fl] = E[ fl ] = E[F] − E[F − fl ] ≥ E[ F] − ε.
The first inequality uses the sandwiching property, and the
last inequality uses the small error property. Similarly,
Em [F ] £ E[F] + ε,
implying that m ε-fools F. Thus a problem about fooling
Ac0 circuits is actually another problem on approximating
circuits with polynomials!
To prove Theorem 1 we will show:
Figure 4. an illustration of sandwiching polynomials (a) and
one-sided approximations (b)–(c).
Lemma 5. Let s ≥ log m be any parameter. Let F be a boolean
function computed by a circuit of depth d and size m. Let m be an
r-independent distribution where
(a)
fu
fl
1
0
F
r ³ r(s, d ) = 3 · 60d+ 3 · (log m)(d+ 1)(d+ 3) · sd(d+ 3),
then
(b)
|Em [F] − E[F]| < ε(s, d),
f0
0
F
1
where ε(s, d) = 0.82s · (10m).
(c)
Theorem 1 follows from Lemma 5 by taking
As mentioned in the overview, one can prove that
k-wise independence fools a function F by constructing an
fl= 1–( 1–¶0)
2
0
F
1