Communications - April 2011

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