Information Technology Reference
In-Depth Information
[
Raz
]
Y
2
d
2
−
d
/
16
2
n
/
2
2
−
n
/
16
(
)
≥
·
≥
·
.
f
,
Z
where the
X
i
's are mutually disjoint,
then a random partition is very unlikely to partition all the
X
i
's into almost equal
parts. This is formalized in the next section to prove the lower bound for multilinear
formulas.
More generally, if
f
=
g
1
(
X
1
)...g
t
(
X
t
)
5.8.2 Lower Bound for Multilinear Formulas
We now present the lower bound for multilinear formulas due to [
Raz09
]. The first
step of our roadmap is to find a suitable normal form for multilinear formulas. The
normal form that we use is from the survey by Shpilka and Yehudayoff [
SY10
].
5.8.2.1 Formulas to Log-Product Sums
The following structural lemma shows that any multilinear formula can be converted
in to a small sum of
log-product
polynomials. The techniques of the following lemma
can also be used in other settings with minor modifications, and we encounter a
different version of this lemma later as well.
Definition 29
Amultilinear polynomial
f
∗ F[
X
]
is called a multilinear log-product
polynomial if
f
=
g
1
...g
t
and there exists a partition of variables
X
=
X
1
∈···∈
X
t
such that
•
g
i
∗ F[
X
i
]
for all
i
∗[
t
]
.
|
X
|
2
|
X
|
•
≥|
X
i
|≥
for all
i,
and
|
X
t
|=
1
.
3
i
3
i
Lemma 30
be a multilinear formula of size s computing a polynomial p.
Then f can be written as a sum of
Let
ʲ
(
+
)
s
1
log-product multivariate polynomials.
Proof
Similar to Lemma 19, let
v
be a node in
ʲ
such that set of variables
X
v
that
|
X
|
2
|
X
|
it depends on satisfies
≥ |
X
v
| ≥
.If
ʲ
v
is the polynomial computed at this
3
3
node, then
f
can be written as
f
=
ʲ
v
·
g
1
+
ʲ
v
=
0
for some
g
1
∗ F[
X
\
X
v
]
.
where
ʲ
v
=
0
is the formula obtained by replacing the node
v
by zero. Note that the
subtree at the node
v
is completely disjoint from
ʲ
v
=
0
. Hence the sum of the sizes
and
|
X
|
3
2
|
X
|
of
ʲ
v
and
ʲ
v
=
0
is at most
s
. Hence,
g
1
∗ F[
X
\
X
v
]
≥ |
X
\
X
v
| ≥
.
3
Inducting on the formulas
ʲ
v
and
ʲ
v
=
0
gives the lemma.
