Information Technology Reference
In-Depth Information
This shows that the
V
1
leaves are not too many. Unfortunately, we cannot imme-
diately bound the number of
V
0
leaves, since we could have a long chain of
V
2
nodes
each with one sibling being a
V
0
leaf. The following observation would show how
we can eliminate such long chains.
Observation 9
Let u be an arbitrary node, and
v
be another node in the subtree
rooted at u with
Leaf
Y
(
u
)
=
Leaf
Y
(v)
. Then the polynomial
g
u
computed at u
and the polynomial
g
v
computed at
v
are related as
g
u
=
f
1
g
v
+
f
2
for some
f
1
,
f
2
∗ F[
X
\
Y
]
.
Proof
If
must have
a
V
0
leaf as the other child. The observation follows as all these nodes are
Leaf
Y
(
u
)
=
Leaf
Y
(v)
, then every node on the path from
u
to
v
+
or
×
gates.
(Obs)
Using the above observation, we shall remove the need for
V
0
nodes completely
by augmenting each node
u
(computing a polynomial
g
u
)in
∈
ʲ
Y
with polynomials
f
(
0
)
f
(
1
)
to enable them to compute
f
(
1
)
f
(
0
)
,
∗ F[
X
\
Y
]
g
u
+
. Let this augmented
u
u
u
u
ʲ
Y
. Using Observation 9, we can now contract any two nodes
u
formula be called
and
, and eliminate all
V
0
nodes completely. Since
all
V
2
nodes are internal nodes, the only leaves of the augmented formula
v
with
Leaf
Y
(
u
)
=
Leaf
Y
(v)
ʲ
Y
are
ʲ
Y
is bounded by 2
|
V
1
|
in
V
1
. Hence, the size of the augmented formula
, which is
bounded by 2
⊩
Leaf
Y
(ʲ)
⊩
by Observation 8.
=
⊟
i
=
1
Suppose
ʲ
computes a polynomial
f
, which can be written as
f
f
i
·
m
i
ʲ
Y
also
with
f
i
∗ F[
X
\
Y
]
and
m
i
's being distinct monomials in
Y
. Since
computes
f
, each
f
i
is a polynomial combination of the polynomials
S
Y
=
f
(
0
)
∗
ʲ
Y
. Since
ʲ
Y
consists of at most 2
⊩
Leaf
Y
(ʲ)
⊩
augmented
f
(
1
)
,
:
u
u
u
4
⊩
Leaf
Y
(ʲ)
⊩
. Therefore,
nodes, we have that td
Y
(
f
)
≥|
S
Y
|≥
4
⊩
Leaf
Y
(ʲ)
⊩
td
Y
(
f
)
=
trdeg
{
f
i
:
i
∗[
t
]} ≥
Hence,
4
r
⊦
r
⊨
⊨
⊩
Leaf
X
i
⊩
[
Kal
]
(ʲ)
=
td
X
i
(
f
i
)
≥
=
O
(
s
).
i
=
1
i
=
1
[
Kal
]
(
5.3.2.2 Lower Bounding
Det
n
)
Lemma 10
Let
X
=
X
1
∈ ··· ∈
X
n
be the partition as defined by
X
t
=
⊞
x
ij
t
mod
n
⊠
. Then,
[
Kal
]
(
n
3
:
−
Det
n
)
=
ˇ(
)
i
j
.
Proof
By symmetry, it is easy to see that td
X
i
(
Det
n
)
is the same for all
i
. Hence, it
n
2
suffices to show that td
Y
(
Det
n
)
=
ˇ(
)
for
Y
=
X
n
= {
x
11
,...,
x
nn
}
.
To see this, observe that the determinant consists of the monomials
x
11
...
x
nn
x
ii
x
jj
·
trdeg
⊞
x
ij
x
ji
j
⊠
=
ˇ(
n
2
x
ij
x
ji
for every
i
∅=
j
. Hence, td
Y
(
Det
n
)
ↆ
:
i
∅=
)
.
[
Kal
]
(
n
3
Therefore,
Det
n
)
=
ˇ(
)
.
The proof of Theorem 5 follows from Lemma 7 and Lemma 10.
