Information Technology Reference
In-Depth Information
v
=
x
1
+
Hence, if
x
2
then
⊣
˃
f
˃
x
1
⊤
⊣
˃
f
˃v
⊤
˃
f
˃
x
1
=
x
2
+
v
=
x
1
+
v
=
x
1
+
x
2
⊣
˃
f
˃
x
2
⊤
⊣
˃
f
˃v
⊤
˃
f
˃
x
2
=
x
2
+
v
=
x
1
+
v
=
x
1
+
x
2
⊣
˃
f
˃
x
i
⊤
˃
f
˃
x
i
=
for
i
>
2
.
v
=
x
1
+
x
2
If
v
=
x
1
·
x
2
, then
⊣
˃
f
˃
x
1
⊤
v
=
x
1
·
x
2
+
⊣
˃
f
˃v
⊤
v
=
x
1
·
x
2
·
˃
f
˃
x
1
=
x
2
⊣
˃
f
˃
x
2
⊤
⊣
˃
f
˃v
⊤
˃
f
˃
x
2
=
x
2
+
x
2
·
x
1
v
=
x
1
·
v
=
x
1
·
⊣
˃
f
˃
x
i
⊤
˃
f
˃
x
i
=
for
i
>
2
.
v
=
x
1
·
x
2
D
(ʲ
)
Hence, by adding at most 5 additional edges to
, we can construct
D
(ʲ)
and hence size of
D
(ʲ)
is at most 5
s
.
(Lemma 4)
5.3.2 Lower Bounds for Formulas
This section is devoted to the proof of Kalorkoti's lower bound [
Kal85
] for formulas
computing
Det
n
,
Perm
n
.
Theorem 5
[
Kal85
]
Any arithmetic formula computing
Perm
n
(or
Det
n
) requires
ˇ(
n
3
)
size.
The exploitableweakness in this setting is again to use the fact that the polynomials
computed at intermediate gates share many polynomial dependencies.
Definition 6
(
Algebraic independence
) A set of polynomials
{
f
1
,...,
f
m
}
is said
to be
algebraically independent
if there is no nontrivial polynomial
H
(
z
1
,...,
z
m
)
such that
H
0.
The size of the largest algebraically independent subset of
f
(
f
1
,...,
f
m
)
=
= {
f
1
,...,
f
m
}
is
called the
transcendence degree
(denoted by trdeg
(
f
)
).
The proof of Kalorkoti's theorem proceeds by defining a
complexity measure
using the above notion of algebraic independence.
The Measure
: For any subset of variables
Y
∧
X
, we can write a polynomial
=
⊟
i
=
1
∗ F[
]
f
i
·
f
X
of the form
f
m
i
where
m
i
's are distinct monomials in the