Information Technology Reference
In-Depth Information
Hence, if
˃
=
k
(
)
denotes the set of
k
-th order partial derivatives of
f
, then the
space spanned by
˃
=
k
f
d
(
)
has dimension 1. This naturally leads us to define
exploiting this weakness.
dim
def
=
˃
=
k
k
(
f
)
(
f
)
It is straightforward to check that
k
is indeed sub-additive and hence
k
(
f
)
≥
s
whenever
f
is computable by a
⃐
circuit of size
s
. For a random polynomial
to be
n
+
k
as there is unlikely to be any linear
dependencies among the partial derivatives. Hence, all that needs to be done is to
find an explicit polynomial with large
k
(
)
f
, we should be expecting
f
k
.
If we consider
Det
n
or
Perm
n
, then any partial derivative of order
k
is just an
(
n
−
k
minor. Also, these minors consist of disjoint sets of monomials and hence
are linearly independent. Hence,
)
×
(
n
−
k
)
Det
n
)
=
k
2
. Choosing
k
k
(
=
n
/
2, we immedi-
circuit computing
Det
n
or
Perm
n
must be of size 2
ˇ(
n
)
.
ately get that any
⃐
5.5.3 Low-Rank
A slight generalization of
⃐
circuits is a
rank-r
circuit
that computes a
polynomial of the form
f
=
T
1
+ ··· +
T
s
where each
T
i
=
i
1
...
id
is a product of linear polynomials such that dim
{
i
1
,...,
id
} ≥
r
.
Thus,
circuit, and a similar partial-derivative technique
for lower bounds works here as well.
In the setting where
r
is much smaller than the number of variables
n
, each
T
i
is
essentially an
r
-variate polynomial masquerading as an
n
-variate polynomial using
an affine transformation. In particular, the set of
n
first-order derivatives of
T
have
rank at most
r
. This yields the following observation.
Observation 12
⃐
is a rank-1
Let T
=
1
...
d
with
dim
{
1
,...,
d
} ≥
r . Then for any k, we
have
⊣
r
⊤
dim
+
k
def
=
˃
=
k
k
(
T
)
(
T
)
≥
.
k
Thus once again by sub-additivity, for any polynomial
f
computable by a rank-
r
·
r
+
r
. Note that a random polynomial
circuit of size
s
,wehave
k
(
f
)
≥
s
close to
n
+
k
k
, which could be much larger for
r
is expected to have
k
(
f
)
⃒
n
.
Det
n
)
=
k
2
. This immediately gives the following lower
bound, the proof of which we leave as an exercise to the interested reader.
We already saw that
k
(
n
2
−
ʻ
for some constant
ʻ >
=
∂
n
ʻ
, where
∂ >
Theorem 13
Let r
≥
0
.Fork
0
is
sufficiently small, we have
