Information Technology Reference
In-Depth Information
(
f
i
)
·
(g
i
)
∧
(
Det
n
)
with FM
FM
FM
. The building blocks are terms of the form
=
·
g
, where FM
(
)
·
(g)
∧
(
Det
n
)
T
.
Since all the monomials in
Det
n
are products of variables from distinct columns
and rows, the rows (and columns) containing the variables
f
depends on is disjoint
from the rows (and columns) containing variables that
g
depends on. Hence, there
exists sets of indices
A
f
f
FM
FM
suc
h
that
f
d
epends only on
⊞
x
jk
B
⊠
,
B
∧[
n
]
:
j
∗
A
,
k
∗
and
g
depends only on
⊞
x
jk
B
⊠
.
Further, since
Det
n
is a homogeneous polynomial of degree
n
, we also have that
both
f
and
g
must be homogen
eo
us a
s w
ell. Also, as all monomials of
g
usin
g
disti
nc
t
row and column indices from
A
and
B
respectively, we see that deg
g
=|
:
j
∗
A
,
k
∗
A
|=|
B
|
|=
ʲ
n
for some
3
2
and deg
f
=|
A
|=|
B
|
. Using Lemma 17, let
|
A
≥
ʲ
≥
3
.This
implies that
(
f
)
≥
(ʲ
n
)
!
, and
(g)
≥
((
1
−
ʲ)
n
)
!
and hence
!
n
/
3
n
(
f
·
g)
≥
(ʲ
n
)
!
((
1
−
ʲ)
n
)
!≥
as
3
≥
ʲ
≥
2
3
.Also,
is clearly sub-additive and we have
!
n
/
3
.
n
(
f
1
g
1
+···+
f
s
g
s
)
≥
s
·
ↆ
n
/
3
=
2
ˇ(
n
)
.
Since
(
Det
n
)
=
n
!
, this forces
s
We only need to prove Lemma 17 now.
5.6.1 Proof of Lemma 17
is homogeneous,
5
and consists
Without loss of generality, assume that the circuit
ʲ
of alternating layers of
gates have fan-in two,
and orient the two children such that the formal degree of the left child is at least as
large as the formal degree of the right child. Such circuits are also called
left-heavy
circuits.
+
and
×
gates. Also, assume that all
×
ʲ
Definition 18
(
Proof tree
) A proof tree of an arithmetic circuit
ʲ
is a sub-circuit
such that
•
ʲ
ʲ
The root of
is in
v
=
v
1
×
v
2
∗
ʲ
,
then
ʲ
as well
.
•
v
1
and
v
2
are in
If a multiplication gate with
v
=
v
1
+···+
v
s
∗
ʲ
,
then exactly one
ʲ
.
•
If an addition gate
v
i
is in
5
It is a forklore result that any circuit can be
homogenized
with just a polynomial blowup in size.
Further, this process also preserves monotonicity of the circuit. A proof of this may be seen in
[
SY10
].
