Communications - April 2011

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