Information Technology Reference
In-Depth Information
be obtained by multiplying some m
i
by arbitrary monomials of degree
is at least
s
N
+
N
−
2
N
+
−
N
.
Proof
For
i
s
,let
A
i
be the set of monomials that can be obtained by
multiplying
m
i
withadegree
=
1
,...,
monomial. By inclusion-exclusion,
⊩
⊩
ↆ
s
⊨
s
⊨
⊩
A
i
ₔ
A
j
⊩
.
A
i
1
|
A
i
| −
i
=
1
i
=
i
<
j
Note that each
A
i
is of size exactly
N
+
N
. Further, since
d
,any
monomial that is divisible by
m
i
and
m
j
must necessarily be divisible by
m
i
and
(
m
i
,
m
j
)
ↆ
the variables in
m
j
not in
m
i
. Hence,
⊩
A
i
ₔ
A
j
⊩
≥
N
+
−
d
. The lemma follows by
N
substituting these above.
Note that any two distinct monomials of NW
k
intersect in at most
k
places. For
each monomial
m
i
of NW
k
,let
m
i
be any nonzero
k
-th order partial derivative of
m
i
.
Therefore,
=
∂
∀
n
. Since we have
n
k
monomials of
m
i
,
m
j
)
ↆ
n
2
(
n
−
2
k
ↆ
for
k
pairwise distance at least
n
2, the above lemma immediately yields a lower bound
for the shifted partials of NW
k
.
/
=
∂
∀
d for some constant
∂ >
Theore
m
56
[
KSS13
]
Let k
0
. Then for any
=
n
2
∀
n
log
n
,
dim
⊣
⊤
⊣
n
2
⊤
n
k
2
·
+
n
2
˃
=
k
ↆ
(
NW
k
)
≥
Sketch of Proof
As mentioned earlier, we have
n
k
monomials
⊞
m
i
⊠
with pairwise
distance at least
n
2
. Using Lemma 55, it suffices to show that
⊣
n
2
⊤
⊣
n
k
2
⊤
⊣
n
2
⊤
n
2
+
n
2
+
−
n
k
·
ↆ
2
·
·
n
2
and this follows easily from standard binomial coefficient estimates.
CombiningwithCorollary 46, we have the lower bound of [
KSS13
] using standard
estimates.
[
O
(
∀
n
)
]
[
∀
n
]
Theorem 57
[
K
S
S13
]
Any
computing the
NW
k
polynomial,
=
∂
∀
n for a sufficiently small
wh
er
e k
∂ >
0
, must have top fan-in
exp
(ˇ
(
∀
n
log
n
))
.
[
KSS13
] used the above lower bound to give an
n
ˇ(
log
n
)
lower bound for a subclass
of formulas called
regular formulas
. The interested reader can refer to [
KSS13
]for
more details.
