Information Technology Reference
In-Depth Information
k
2
exp
n
ʻ
)
r
+
k
=
ˇ(
.
Hence, any rank-r
circuit computing
Det
n
or
Perm
n
must have size
exp
ˇ(
n
ʻ
)
.
This technique of using the rank of partial derivatives was introduced by Nisan
and Wigderson [
NW97
] to prove lower bounds for
homogeneous depth-
3
circuits
(which also follows as a corollary of Theorem 13). The survey of Chen, Kayal and
Wigderson [
CKW11
] give a comprehensive exposition of the power of the
partial
derivative method
.
With these simple examples, we can move on to other lower bounds for various
other more interesting models.
5.6 Lower Bounds for Monotone Circuits
This section presents a slight generalization of a lower bound by Jerrum and
Snir [
JS82
]. To motivate our presentation here, let us first assume that the underlying
field is
R
, the field of real numbers. A monotone circuit over
R
is a circuit having
+
,
×
gates in which all the field constants are
nonnegative
real numbers. Such a cir-
cuit can compute any polynomial
f
over
R
all of whose coefficients are nonnegative
real numbers, such as for example the permanent. It is then natural to ask whether
there are small monotone circuits over
computing the permanent. Jerrum and Snir
[
JS82
] obtained an exponential lower bound on the size of monotone circuits over
R
R
computing the permanent. Note that this definition of monotone circuits is valid only
over
(actually more generally over ordered fields but not over say finite fields) and
such circuits can only compute polynomials with nonnegative coefficients. Here we
will present Jerrum and Snir's argument in a slightly more generalized form such that
the circuit model makes sense over any field
R
F
and is complete, i.e., can compute any
polynomial over
. Let us first explain the motivation behind the generalized circuit
model that we present here. Observe that in any monotone circuit over
F
R
, there is
no cancellation as there are no negative coefficients. Formally, for a node
v
in our
circuits let us denote by
f
the polynomial computed at that node. For a polynomial
v
f
let us denote by Mon
(
f
)
the set of monomials having a nonzero coefficient in the
polynomial
f
.
1. If
w
=
u
+
v
then
Mon
(
f
w
)
=
Mon
(
f
u
)
∃
Mon
(
f
v
).
2. If
w
=
u
×
v
then
def
= {
Mon
(
f
w
)
=
Mon
(
f
u
)
·
Mon
(
f
v
)
m
1
·
m
2
:
m
1
∗
Mon
(
f
u
),
m
2
∗
Mon
(
f
v
)
}
.
