Information Technology Reference
In-Depth Information
5.7 Lower Bounds for Depth-3 Circuits over Finite Fields
This section presents the lower bound of Grigoriev andKarpinski [
GK98
]for
Det
n
.A
follow-up paper of Grigoriev and Razborov [
GR00
] extended the result over function
fields, also including a weaker lower bound for the permanent, but we shall present
a slightly different proof that works for the permanent as well.
Theorem 20
[
GK98
]
Any depth-3 circuit computing
Det
n
(or
Perm
n
) over a finite
field
2
) requires size
2
ˇ(
n
)
.
F
q
(q
∅=
Main idea
:Let
q
=|F|
. Suppose
C
=
T
1
+···+
T
s
, where each
T
i
is a product of
linear polynomials. Define rank
as in Sect.
5.5.3
to be the dimension of the set
of linear polynomials that
T
i
is a product of.
In Sect.
5.5.3
, we saw that the dimension of partial derivatives would handle
low
rank T
i
's. As for the high rank
T
i
's, since
T
i
is a product of at least
r
linearly inde-
pendent linear polynomials, a random evaluation keeps
T
i
nonzero with probability
(
T
i
)
at most
1
q
r
. Since
q
is a constant, we have that a random evaluation of a high
rank
T
i
is almost always zero. Hence, in a sense,
C
can be “approximated” by just
the low-rank components.
Grigoriev and Karpinski [
GK98
] formalize the above idea as a measure by com-
bining the partial derivative technique seen in Sect.
5.5.3
with evaluations to show
that
Det
n
cannot be approximated by a low-rank
1
−
circuit.
5.7.1 The Complexity Measure
For any polynomial
f
∗ F[
x
11
,...,
x
nn
]
, define the matrix
M
k
(
f
)
as follows—the
columns of
M
k
(
f
)
are indexed by
k
-th order partial derivatives of
f
, and rows by
n
2
, with the entry being the evaluation of the partial derivative (column
index) at the point (row index).
The rank of
M
k
(
elements of
F
could be a possible choice of a complexity measure but
Grigoriev and Karpinski make a small modification to handle the high rank
T
i
s.
Instead, they look at the matrix
M
k
(
f
)
and remove a few
erroneous
evaluation points
and use the rank of the resulting matrix. For any
f
)
n
2
A
∧ F
, let us define
M
k
(
f
;
A)
to be the matrix obtained from
M
k
(
f
)
by only taking the rows whose indices are in
[
GK
]
A
. Also, let
k
,A
(
f
)
denote rank
(
M
k
(
f
;
A))
.
5.7.2 Upper Bounding
[
GK
]
for a Depth-3 Circuit
k
,A
Our task here is to give an upper bound on the complexity measure for a
-circuit
of size
s
. We first see that the task reduces to upper bounding the measure for a single
term via subadditivity. It follows from the linearity of the entries of the matrix.
