Information Technology Reference
In-Depth Information
•
1
,...,
2
k
−
1
that are roughly equally spaced between the
first and the last layer. These layers, and the first and the last layers, shall be
untouched and shall be called
pristine layers
.
(
−
)
Select
2
k
1
layers
•
In all the other layers, retain only those edges connecting vertex
i
of this layer to
vertex
i
of the next.
This restriction effectively makes the graph similar to an ABP with 2
k
+
1 layers. Let
the polynomial computed by the restricted ABP be IMM
n
,
d
(
. Since IMM
n
,
d
was
obtained by just setting some variables of IMM
n
,
d
to zero, the dimension of shifted
partial derivatives of IMM
n
,
d
can only be smaller than that of IMM
n
,
d
. Similar to
Observation 60, we have the following observation.
x
)
Observation 61
For every choice of k edges from odd-numbered pristine layers,
there is a unique source-sink path that passes through them.
In other words, for any choice of k variables chosen by picking one from each
odd-numbered pristine layer, then the k-th order partial derivative of
IMM
n
,
d
with
respect to these k variables is a nonzero monomial.
Once again, we can lower bound the dimension of shifted partial derivatives of
IMM
n
,
d
by a monomial counting problem. Similar to the earlier case, [
FLMS13
]
show that the monomials thus obtained are
far
from one another. We state their main
lemma below without proof.
Lemma 62
[
FLMS13
]
There are at least n
k
/
2
monomials of
IMM
n
,
d
of pairwise
n
distance at least
4
.
Again, using Lemma 55 and standard binomial coefficient estimates, this implies
that the shifted partial derivatives of IMM
n
,
d
is almost as large as the trivial upper
bound.
=
∂
∀
d for a sufficiently small
∂ >
Theorem 63
[
FLMS13
]
Let k
0
and
be an
N
+
integer such that n
1
/
16
n
1
/
4
where N is the number of variables
IMM
n
,
d
≥
≥
depends on. Then,
dim
⊣
⊤
dim
⊣
⊤
˃
=
k
IMM
n
,
d
˃
=
k
IMM
n
,
d
ↆ
≥
≥
⊣
n
k
/
2
⊣
N
⊤⊤
+
=
ˇ
·
.
Combining with Corollary 46, we get the lower bound of [
FLMS13
].
[
O
(
∀
d
)
]
[
∀
d
]
Theorem 64
[
FLMS13
]
Any
circuit com
p
uting
IMM
n
,
d
, with
(ˇ(
∀
d
log
n
n
ʻ
for a sufficiently small
ʻ >
d
≥
0
, has top fan-in
exp
))
.
Similar to [
KSS13
], the above result also implies
n
ˇ(
log
n
)
lower bounds for regular
formulas computing IMM
n
,
d
.
