Information Technology Reference
In-Depth Information
sequence of
m
, denoted by
ˇ(
)
(
−
)
-increasing sequence of
m
that is entirely
contained in
D
2
and is ordered highest according to the ordering
'
m
,as
n
k
≡
'
.If
m
contains no
(
-increasing sequence entirely in
D
2
, then we shall say the canonical increasing
sequence is empty.
n
−
k
)
The reason we restrict ourselves to
D
2
is because it is easier to understand which
monomials change the canonical increasing sequence and which monomials do not.
Lemma 50
-increasing sequence completely contained in D
2
,
and let m
S
be the monomial obtained by multiplying the variables indexed by S.
There are at least
Let S be an
(
n
−
k
)
(
2
(
n
−
k
)
−
1
)
variables in D
2
such that if m is any monomial
over these variables, then
ˇ(
m
S
)
=
ˇ(
m
·
m
S
)
.
Proof
Note that for any
x
i
,
j
D
2
other than
x
n
,
n
, exactly one of
x
i
+
1
,
j
or
x
i
,
j
+
1
is in
D
2
as well; let us refer to this element in
D
2
as the
companion
of
x
i
,
j
.Itis
straightforward to check that for any
∗
-increasing sequence
S
, the elements of
S
and their companions do not alter the canonical increasing sequence.
(
n
−
k
)
It is a simple exercise to check that the number of
(
n
−
k
)
-increasing sequences
contained in
D
2
is
n
+
k
2
k
. Further, as we are free to use the
n
2
−
+
2
n
1 variables
(
−
)
−
outside
D
2
, and the 2
1 variables that don't alter the canonical increasing
sequence, we have the following lemma.
n
k
Lemma 51
For any k
,
ↆ
0
,
dim
⊣
˃
=
k
⊤
⊣
n
⊤⊣
(
⊤
n
2
+
k
−
2
n
+
1
)
+
2
(
n
−
k
)
−
1
+
(
Det
n
)
ↆ
.
2
k
≥
Although this lower bound is not as large as expected for a random polynomial,
this is s
til
l sufficient to give strong lower bounds f
or
depth-4 circuits. By choosing
k
n
2
∀
n
, Lemma 51 with Corollary 46
yields the lower bound of Gupta, Kamath, Kayal and Saptharishi [
GKKS13
]
=
∂
∀
n
for a small enough
∂ >
0, and
=
[
O
(
∀
n
)
]
[
∀
n
]
Theorem
52
Any
circuit computing
Det
n
or
Perm
n
has top
fanin
2
ˇ(
∀
n
)
.
It is worth noting that alt
h
ough Claim 47 suggests that we should be able to obtain
a lower bound of exp
(ˇ(
∀
n
log
n
for
Det
n
,[
GKKS13
] also showed that the above
estimate for the dimension of shifted partial derivatives for the determinant is fairly
tight. Hence the dimension of shifted partials cannot give a stronger lower bound
for the determinant polynomial. However, it is possible that the estimate is
not
tight
for the permanent and the dimension of shifted partial derivatives of the permanent
is provably strictly larger than that
of
the determinant! It is conceivable that one
should be able to prove an exp
))
(ˇ(
∀
n
log
n
))
lower bound for the permanent using
this measure.
Indeed, subsequently an exp
∀
d
log
n
was proved [
KSS13
,
FLMS13
]for
other explicit polynomials which we now outline.
(ˇ(
))
