Circuit Complexity - Models of Computation: Exploring the Power of Computing - page 449

g 1 , g 2 , ... , g m can be represented by 1 g m ) using DeMorgan's

Rules, both AND and OR of g 1 , g 2 , ... , g m have the same degree. We find an approximating
polynomial for both AND and OR by approximating the OR gate.
We approximate the OR of g 1 , g 2 , ... , g m by creating subsets S 1 , S 2 , ... , S k of

− − g 1 )( 1 − g 2 ) ··· −

( 1 ( 1

{ g 1 , g 2 ,

,computing f i =( j∈S i g j ) 2 , and combining these results in
OR ( f 1 , f 2 , ... , f k )= 1

... , g m }

− ( 1 − f 1 )( 1 − f 2 ) ··· ( 1 − f k )

The degree of this approximation is 2 k times the maximal degree of any polynomial in the
set or at most ( 2 k ) d , the desired result.

There is no error in this approximation if the original OR has value 0. We now show
that there exist subsets S 1 , S 2 , ... , S k such that the error is at most 2 n−k when the original
OR has value 1. Let's fix on a particular input n -tuple x to the circuit. Suppose each subset
is formed by deciding for each function in

{ g 1 , g 2 , ... , g m }

{ g 1 , g 2 , ... , g m }

with probability 1 / 2whether

is 1 on x , the probability
of choosing a function for set whose value is 1 is at least 1 / 2. Thus, the probability that
OR ( f 1 , f 2 , ... , f k ) has value 0 when the original OR has value 1 is the probability that each
of f 1 , f 2 , ... , f k has value 0, which is at most 2 −k .Sincethesets

{ g 1 , g 2 , ... , g m }

or not to include it in the set. If one or more of

result
in an error on input x with probability at most 2 −k , the average number of errors on input
x , averaged over all choices for the k sets, is at most 2 −k and the average number of errors
on the set of 2 n

{ S 1 , S 2 , ... , S k }

inputs is at most 2 n−k . It follows that some set { S 1 , S 2 , ... , S k } (and

a corresponding approximating function) has an incorrect value on at most 2 n−k inputs.

1 ) 2 n−k errors occur on all but the
output gate, at most size ( C ) 2 n−k errors occur on the entire circuit.
The next result demonstrates that a √ n -approximator (obtained by letting k = n 1 / 2 d / 2)
and the parity function must differ on many inputs. This is used to show that the circuit being
approximated must have many gates.

Since by the inductive hypothesis at most ( size ( C ) −

be a √ n -approximator for f ( n )
⊕

LEMMA 9.7.7 Let f : B .Then, f and f ( n )

⊕

n

→B differ on at

least 2 n / 50 input n -tuples.
Proof Let U

n be the n -tuples on which the functions agree. We derive an upper

⊆B

of β =( 49 ) 2 n / 50 that implies the lower bound of the lemma. We derive
this bound indirectly. Since there are 3 |U|

| U |

bound on

, assign each one
a different polynomial and show that the number of such polynomials is at most 3 β ,which
implies that

functions g : U →{− 1, 0, 1 }

β .
Transform the polynomial in the variables x 1 , x 2 , ... , x n representing f ( n )

| U |≤

by mapping

⊕

1. (Observe that y i = 1.) It
does not change the degree of a polynomial. In these new variables f ( n )
⊕

x i to y i = 2 x i − 1. This mapping sends 1 to 1 and 0 to −

can be represented

exactlybythepolynomial y 1 y 2 ··· y n .

n

Given a function g : U →{− 1, 0, 1 } , extend it arbitrarily to a function g : B →

{− 1, 0, 1 } .Let p be a polynomial in Y = { y 1 , y 2 , ... , y n } that represents g on U exactly.

Let cy i 1 y i 2 ··· y i t be a term in p for some constant c ∈{− 1, 1 } . We show that if t is larger

than n/ 2 we can replace this term wi th a smaller-degree term.
Let T =

y i t can be written
as c Π T ,whereby Π T w e mean the product of all terms in T .With y i = 1, this m ay
be rewritten as c Π Y Π T .Since f ( n )
⊕

{ y i 1 , y i 2 , ... , y i t } and T = Y − T .Theterm cy i 1 y i 2 ···

=Π Y ,ontheset U this is equivalent to c f Π T ,