Let

f ¢ := f · ( 1 − E˜ν).

Then f ¢ = 0 whenever F ¢ = 0. It remains to estimate F ¢ – f 2 2:

function computed by a circuit of depth d and size m. Let m be an
r-independent distribution where
r ³ 3 · 60d+ 3 · (log m)(d+ 1)(d+ 3) · sd(d+ 3),

then

Em [F ] > E[F ] − ε(s, d)

where ε(s, d) = 0.82s · (10m).

which completes the proof.



Proof. Let F¢ be the boolean function and let fl ¢ be the
polynomial from Lemma 9. The degree of fl ¢ is < r. We use the
fact that since m is r-independent, Em[ fl ¢] = E[ fl ¢] (since k-wise
independence fools degree-k polynomials, as discussed
above):
We can no w use Lemma 8 to give each Ac0 function F a lower
sandwiching polynomial, at least after a little “massaging”:
Lemma 9. For every boolean circuit F of depth d and size m and
any s ³ log m, and for any probability distribution m on {0, 1} there
is a boolean function F¢ and a polynomial fl¢ of degree less than
rf = 3 · 60d+ 3 · (log m)(d+ 1)(d+ 3) · sd (d+ 3)

such that

• Pm[F ¹ F¢] < ε (s, d)/2, • F ¢ F¢ on {0, 1}n, • fl ¢ £ F¢ on {0, 1}n, and

• E [F¢ – fl ¢] < ε (s, d)/2,

where ε(s, d) = 0.82s · (10m).

Proof. Let F¢ be the boolean function and let f ¢ be the polynomial from Lemma 8 with s1 = s and s2»60d+ 3·(log m) (d+ 1)(d+ 3)·sd(d+ 3). The first two properties follow directly from the lemma. Set

fl ¢ := 1 - ( 1 - f ¢) 2.

It is clear that fl ¢ £ 1 and moreover fl ¢ = 0 whenever F¢ = 0, hence fl ¢ £ F¢. Finally, F¢(x) - fl ¢(x) = 0 when F¢(x) = 0, and is equal to

F¢(x) - fl ¢(x) = ( 1 - f ¢(x)) 2 = (F¢(x) - f ¢(x)) 2

when F¢(x) = 1, thus

E[F¢ − fl ¢ ] < F ¢ –f ¢ 2 2 < 0.82s · (5m) = ε(s, d)/2

by Lemma 8. To finish the proof we note that the degree of fl ¢ is bounded by

2 · deg (f ¢) £ 2 · ((s1 · log m)d + s2 ) < 2. 5 · s2 < rf .



Lemma 9 implies the following:

Em [F] ³ Em [F¢] − Pm [F ¹ F¢] > Em[ fl ¢] − ε(s, d)/2 = E[ fl ¢] − ε (s, d)/2 = E[F ¢] − E[F ¢ − fl ¢ ] − ε(s, d)/2 ³ E[F ¢] − ε (s, d) ³ E[F ] − ε(s, d).



The dual inequality to Lemma 10 follows immediately by applying the lemma to the negation F

−

= 1 −F of F. We have

Em[F

−

] > E[F

−

] − ε(s, d), and thus

Em[F] = 1 − Em[F

−

] < 1 − E[F

−

] + ε(s, d) = E[F] + ε(s, d).

Together, these two statements yield Lemma 5.

References

1. alon, n., babai, l., and Itai, a. a fast and simple randomized parallel algorithm for the maximal independent set problem. J.  Algorithm. 7, 4 (1986), 567–583.

2. bazzi, l. M.J. Polylogarithmic independence can fool dnF formulas. SIAM J. Comput. (2009), to appear.

3. braverman, M. Polylogarithmic independence fools ac0 circuits. J.  ACM 57, 5 (2010), 1–10.

4. de wolf, r. A Brief Introduction to Fourier Analysis on the Boolean Cube. number 1 in Graduate surveys. theory of computing library, 2008.

5. Furst, M., saxe, J., sipser, M. Parity, circuits, and the polynomial-time hierarchy. Theor. Comput. Syst. 17, 1 (1984), 13–27.

6. hastad, J. almost optimal lower bounds for small depth circuits.

In Proceedings of the Eighteenth Annual ACM Symposium on Theory of Computing (1986), acM, ny, 20.

7. Joffe, a. on a set of almost deterministic k-independent random variables. Ann. Probab. 2, 1 (1974), 161–162.

8. linial, n., Mansour, y., nisan, n. constant depth circuits, Fourier

 

Mark Braverman, university of toronto.

transform, and learnability. J. ACM 40, 3 (1993), 607–620.

9. linial, n., nisan, n. approximate inclusion-exclusion. Combinatorica 10, 4 (1990), 349–365.

10. nisan, n. Pseudorandom bits for constant depth circuits. Combinatorica 11, 1 (1991), 63–70.

11. razborov, a.a. lower bounds on the size of bounded-depth networks over a complete basis with logical addition. Math. Notes Acad. Sci. USSR 41, 4 (1987), 333–338.

12. razborov, a.a. a simple proof of bazzi’s theorem. In Electronic Colloquium on Computational Complexity. report tr08-081, 2008.

13. smolensky, r. algebraic methods in the theory of lower bounds for boolean circuit complexity. In Proceedings of the Nineteenth Annual ACM Symposium on Theory of Computing (STOC’ 87) (1987), acM, ny, 77–82.

14. Valiant, l. G., Vazirani, V. V. nP is as easy as detecting unique solutions. In Proceedings of the Seventeenth Annual ACM Symposium on Theory of Computing (S TOC’ 85) (1985), acM, ny, 458–463.

Lemma 10. Let s ³ log m be any parameter. Let F be a boolean © 2011 acM 0001-0782/11/04 $10.00