5. 1 Proof of Lemma 5
The proof will combine the two types of polynomial approximations that we discussed in Sections 3 and 4. When we
produced the almost-everywhere-correct polynomials in
Section 4 we noted that when the polynomial f does disagree
with F, the disagreement might be very large. It is still possible to give the following very crude bound on the maximum
value f ∞ that | f | may attain on {0, 1}n:
Figure 5. the proof of Lemma 8.
(a)
¶
1
0
F
Claim 7. In Lemma 4, for s ³ log m,
(b)
Eν
f ∞ < (2m)deg( f )− 2 = (2m)(s·log m)d − 2.
1
0
F
The claim follows by an easy induction from the proof of
Lemma 4. We omit the proof here.
A low-degree polynomial f0 is a one-sided approximation
of a boolean F (see Figure 4(b) ) if:
(c)
F;=F∨E ν
1
0
F
(d)
• f0 is a good approximation: F – f0 22 is small.
• f0’s error is one-sided: f0(x) = 0 whenever F(x) = 0.
1–Eν
1–
1
0
Eν
If F had such an approximation, then the polynomial fl := 1 −
( 1 − f0)
2 would be a (lower) sandwiching polynomial for F. fl
still has a low degree, and
(e)
¶;=¶◊( 1– ) Eν
F;
1
0
E[F −fl ] = F–f0 22
is small. This process is illustrated in Figure 4(c).
Thus, being able to produce one-sided approximations
(that combine characteristics from both Sections 3 and 4
approximations) would be enough. Unfortunately, we are
unable to construct such polynomials. Instead, we show
how to modify F just a little bit to obtain a boolean func-
tion F¢. The change is slight enough with respect to both m
and the uniform measure so that fooling F¢ and fooling F is
almost equivalent. We then show that the modified F¢ does
have a one-sided approximation f ¢. The properties of F¢ and
f ¢ are summarized in the following lemma:
Lemma 8. Let F be computed by a circuit of depth d and size
m. Let s1, s2 be two parameters with s1 · log m. Let m be any prob-
ability distribution on {0, 1}n, and U {0, 1}n be the uniform distri-
bution on {0, 1}n. Set
Let Eν be the function from Lemma 4 with s = s1. Set F ¢ = F ∨ Eν.
Then there is a polynomial f ¢ of degree rf £ (s1 · log m)d + s2, such
that
• F ≤ F¢ on {0, 1}n;
• Pm[F ¹ F¢ ] < 2 . 0.82s1m;
• F¢ – f ¢
2
2 < 0.82 s1 ·(4m) + 22. 9(s1·log m) d log m − s2 1/(d+ 3)/20, and
• f ¢(x) = 0 whenever F¢ (x) = 0.
Proof idea: The proof is illustrated on Figure 5. We start
with a polynomial approximation f for F that works “almost
everywhere”. By Lemma 4 we know that there is an Ac0 function Eν that “flags” the locations of all the errors. We fix F ¢=
F ∨ Eν so that f = 0 whenever F ¢ = 0. The problem is that the
error |F¢ − f |
2 may be large in the area where E ν = 1 (and thus f
behaves poorly). If we could multiply f ¢ = f ¢·( 1 − E ν), we would
be done, as this would “kill” all the locations where Eν is 1.
Unfortunately, we cannot do this since Eν is not a low degree
polynomial. Here we use the fact that E ν is itself an Ac0 function, and thus can be approximated well by a polynomial E˜ν by
the Linial–Mansour–Nisan approximation (Lemma 2). A brief
calculation indeed shows that f ¢ = f · ( 1 − E˜ν) for an appropriately chosen E˜ν satisfies all the conditions.
Proof. The first property follows from the definition of
F¢. The second one follows from Lemma 4 directly, since
Pm [Eν = 1] ≤ 2 · Pν [Eν = 1] < 2 · 0.82s1 m.
Note also that
P[Eν = 1] ≤ 2 · Pν [Eν = 1] < 2 · 0.82s1 m.
Let f be the approximating polynomial for F from that
lemma, so that F = F ¢ = f whenever Eν = 0, and thus f = 0 whenever F ¢ = 0. By Proposition 7 we have
f ∞<(2m)(s1·logm)d< 21. 4(s1·logm)dlogm.
We let E˜ν be the low degree approximation of Eν of degree s2.
By Linial et al.
8 (Lemma 2 above), we have
E ν - E˜ν
2
2 < O (m3) · 2 − s2 1/(d+ 3)/20.