Information Technology Reference
In-Depth Information
Observation 42
Any k-th order partial derivative of Q
d
is of the form Q
d
−
k
p where
p is a polynomial of degree at most k. Hence, if k
⃒
d, then all k-th order partial
derivatives of Q
d
share large common factors.
This suggests that instead of looking at linear combinations of the partial deriv-
atives of
Q
d
, we should instead be analyzing
low-degree polynomial combinations
of them.
Definition 43
Let
˃
=
k
(
f
)
refer to the set of all
k-th
order partial derivatives of
f
,
and
x
≥
refer to the set of all monomials of degree at most
. The shifted partials
of
f
, denoted by
˃
=
k
)
≥
, is the vector space spanned by
⊞
x
≥
·
˃
=
k
)
⊠
.The
(
f
(
f
[
Kay
]
k
dimension of this space shall be denoted by
.
The above observation shows that any element of
˃
=
k
Q
d
≥
(
f
)
,
is divisible by
Q
d
−
k
and we thereby have the following lemma.
)
≥
n
+
k
+
n
,the
[
Kay
]
k
Q
d
Lemma 44
If f
=
where Q is a quadratic, then
(
f
,
number of monomials of degree
(
k
+
)
.
Note that if
f
was instead a random polynomial, we would expect the measure
dim
˃
=
k
to be about
n
+
n
·
n
+
n
, which is
much
larger than
n
+
k
+
)
≥
for
(
f
n
[
Kay
]
k
suitable choice of
k
is certainly potentially useful for
this model. Very similar to the above lemma, one can also show the following upper
bound for the
building blocks
of
,
. Hence this measure
,
[
a
]
[
b
]
circuits.
=
Q
1
...
≥
Lemma 45
Let f
Q
a
with
deg
Q
i
b for all i . Then,
dim
⊣
⊤
⊣
a
k
⊤⊣
n
⊤
+
(
b
−
1
)
k
+
[
Kay
]
k
,
˃
=
k
(
f
)
=
(
f
)
≥
.
n
≥
[
Kay
]
k
It is easy to check that
is a sub-additive measure, and we immediately have
,
this corollary.
[
a
]
[
b
]
circuit
Corollary 46
Let f be an n-variate polynomial computed by a
of top fan-in s. Then,
⊣
a
k
⊤⊣
n
⊤
.
+
(
b
−
1
)
k
+
[
Kay
]
k
(
f
)
≥
s
·
,
n
[
a
]
[
b
]
Or in other words for any choice of k
,
, we have that any
circuit
computing a polynomial f must have top fan-in s at least
[
Kay
]
k
)
k
n
+
(
b
−
1
)
k
+
(
f
,
.
n
