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
 
Search WWH ::




Custom Search