Information Technology Reference
In-Depth Information
<
/
ʲ
Proof
If
d
n
100, then the lemma is vacuously true. Since
is a formula of
>
/
depth
and computes a polynomial of degree
d
n
100, there must be at least one
of fan-in at least
100
1
/
=
t
2
. Then similar to Lemma 30,
product gate
v
f
+
ʲ
v
=
0
f
=
ʲ
v
·
is a product of
t
2
polynomials, by grouping the factors together we have that
As
ʲ
v
f
is a multilinear
t
-product. Further,
ʲ
v
·
ʲ
v
=
0
is a multilinear polynomial that is
computable by a depth-
formula of smaller size and we can induct on
ʲ
v
=
0
.
Lemma 38
Let
f
(
X
)
be an n-variate polynomial computed by a depth-
mul-
tilinear formula of size s. If X
=
Y
∈
Z is a randomly chosen partition with
n
ˇ(
1
/)
))
|
Y
|=|
Z
|=
n
/
2
, then with probability at least
(
1
−
s
·
exp
(
−
we have
[
Raz
]
Y
2
n
/
2
n
ˇ(
1
/)
).
(
f
)
≥
(
s
+
1
)
·
·
exp
(
−
,
Z
Sketch of Proof
By Lemma 37, we have that
f
can be written as
g
0
+
g
1
+···+
g
s
where deg
100 and
g
1
,...,g
s
are multilinear
t
-products. Note that since
g
0
is a multilinear polynomial of degree at most
(g
0
)
≥
n
/
(
n
/
100
)
, the number of monomials
in
g
0
is at most
100
≥
n
[
Raz
]
Y
2
n
/
10
.
For the other
g
i
's, we can bound the probability that
2
n
/
10
. Hence,
(g
0
)
≥
n
/
,
Z
[
Raz
]
Y
is large in a very
similar fashion as in Lemma 32, as the probability that all the factors of
g
i
are
partitioned in a balanced manner is roughly the intersection of
t
independent events.
By very similar estimates, this probability can be bounded by
(g
i
)
,
Z
t
. Hence,
(
/
(
))
1
poly
n
with high probability
[
Raz
]
Y
)
≥
[
Raz
]
Y
(g
0
)
+···+
[
Raz
]
2
n
/
2
n
ˇ(
1
/)
).
(
f
(g
s
)
≥
(
s
+
1
)
·
·
exp
(
−
,
Z
,
Z
Y
,
Z
Combining Lemma 38 with Lemma 34, we have the following theorem of Raz
and Yehudayoff.
Theorem 39
[
RY09
]
Any multilinear formula of depth
computing
Det
n
or
Perm
n
n
ˇ(
1
/)
)
must be of size
exp
(
.
5.9 Lower Bounds for Depth-4 Circuits
This section addresses a recent technique for proving lower bounds for some depth-4
circuits.
Definition 40
A depth-4 circuit, also referred to as a
circuit, computes a
polynomial of the form
=
Q
11
...
Q
1
d
+ ··· +
Q
s
1
...
Q
sd
.
f
