Information Technology Reference
In-Depth Information
PERFORMANCE OF APPROXIMATOR CIRCUITS
We now show that when the approximation pro-
cess is complete, the approximation circuit for
f
(
n
)
clique
,
k
makes a very large number of errors
but that each gate approximation introduces a small number of errors. Thus, many gates must
have been approximated to produce the large number of errors made by the fully approximated
circuit. In fact, we show that the approximating circuit for
f
(
n
)
clique
,
k
either has output identi-
cally 0, thereby making one error on each of the
τ
+
=
k
positive test inputs (it produces 0
when it should produce 1), or makes
τ
−
/
2errorsonthe
τ
−
negative test inputs (it produces
1 when it should produce 0). On the other hand, we also show that approximating one
AND
or
OR
gate causes a small number of errors, at most
e
AND
errors per
AND
gate on positive
test inputs and at most
e
OR
errors per
OR
gate on negative test inputs, quantities for which
upper bounds are derived below. It follows that the original circuit for
f
(
n
)
clique
,
k
either has at
least
τ
+
/e
AND
AND
gates or at least
τ
−
/
(
2
e
OR
)
OR
gates. The lower bound on the monotone
circuit size of
f
(
n
)
clique
,
k
is the larger of these two lower bounds.
LEMMA
9.6.6
Let
k ≤ n
+
1
. Then any approximation circuit for
f
(
n
)
clique
,
k
either computes a
function that is identically zero or makes errors on half of the
k
-negative test inputs.
Proof
Lettheapproximationcircuitfor
f
(
n
)
clique
,
k
f
(
n
)
clique
,
k
.Ifthis
function is identically zero, we are done. Suppose not. Since the output gate in the original
circuit is an
AND
gate, the function
compute the function
f
(
n
)
clique
,
k
is represented by a SOPE in which each term
is the product of variables whose endpoint set (the vertices involved) has size at most
p
.
Because
f
(
n
)
clique
,
k
f
(
n
)
t
.
An error is made on a negative test input if
t
=
1. But this happens only if each of the
endpoints in
E
(
t
)
is in a different set of the
(
k
is not identically zero, there is a non-zero term
t
such that
clique
,
k
≥
−
1
)
-balanced partition defining the negative
test input.
Let
φ
be the fraction of the negative test inputs on which
t
=
1. We derive a lower
bound to
φ
by deriving an upper bound on the fraction
χ
of the
(
k
1
)
-balanced partitions
with the property that two or more vertices in
E
(
t
)
fall into the same set. It follows that
φ
−
χ
.
To simplify bounding
χ
, we use the one-to-one correspondence developed in the proof
of Lemma
9.6.5
between the
n
vertices in
V
=
≥
−
1
{
1, 2, 3,
...
,
n
}
P
and the pairs
associated
with a
(
k
1
)
-balanced partition. Since
E
(
t
)
has at most
p
vertices, the number of ways to
assign two vertices from
E
(
t
)
to pairs in
−
so that two of them fall into the same set,
N
2
,
is at most the number of ways to choose two vertices from a set of
p
vertices,
p
(
p
P
−
1
)
/
2,
P
,
m
2
, and the number
times the number of ways of assigning these two vertices to pairs in
of ways of assigning the remaining
n
2
)!
.Here
m
2
is at most the product
of the number of ways of choosing a pair for the first vertex,
(
k
−
2vertices,
(
n
−
−
1
)
n/
(
k
−
1
)
,andthe
n/
(
k
−
1
)
−
number of ways of choosing a pair for the second from the same set,
1. Thus,
N
2
is at most
(
p
(
p
−
1
)
/
2
)(
k
−
1
)
n/
(
k
−
1
)
(
n/
(
k
−
1
)
−
1
)(
n
−
2
)!
, which is at most
p
2
n/
(
k
−
1
)
(
n
−
1
)!
/
2. Since there are
n
!
assignments of vertices in
V
to pairs in
P
,
(
k
p
2
χ
≤
n/
(
k
−
1
)
/
(
2
n
)
.Because
p
=
−
1
)
/
2
,
χ
is at most 1
/
4since
k
−
≤
n
.
1
We now derive upper bounds on the number of errors introduced through the approxima-
tion of individual
AND
and
OR
gates. Since we have assumed that
AND
and
OR
gates alternate
on any path between inputs and outputs, it follows that the inputs
f
l
and
f
r
to an
AND
gate
Search WWH ::
Custom Search