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