Information Technology Reference
In-Depth Information
=
∈
Observation 25
(Sub-additivity)
For any partition X
Y
Z and any pair of
[
Raz
]
Y
[
Raz
]
Y
multilinear polynomials f and
g
in
F[
]
(
+
g)
≥
(
)
+
X
we have
f
f
,
Z
,
Z
[
Raz
]
Y
(g)
.
,
Z
Proof
Follows from the linearity of the matrix.
Observation 26
(Multiplicativity)
If
f
1
∗ F[
Y
1
,
Z
1
]
and
f
2
∗ F[
Y
2
,
Z
2
]
with
Y
=
Y
1
∈
Y
2
and Z
=
Z
1
∈
Z
2
, then
[
Raz
]
Y
f
2
)
=
[
Raz
]
f
1
)
·
[
Raz
]
(
f
1
·
Z
1
(
Z
2
(
f
2
).
,
Z
Y
1
,
Y
2
,
Proof
It is not hard to see that
M
Y
,
Z
(
f
1
·
f
2
)
is the tensor product
M
Y
1
,
Z
1
(
f
1
)
ₒ
M
Y
2
,
Z
2
(
f
2
)
, and the rank of a tensor product of two matrices is the product of the
ranks.
[
Raz
]
Y
2
min
(
|
Y
|
,
|
Z
|
)
.
Observation 27
(
f
)
≥
,
Z
Proof
The number of rows is 2
|
Y
|
and number of columns is 2
|
Z
|
, and hence the rank
is upper bounded by the minimum.
Let us get back to lower bounds for multilinear models, and attempt to use
[
Raz
]
Y
(
f
)
defined above. Unfortunately, there are examples of simple polynomi-
,
Z
[
Raz
]
Y
2
n
. Raz's idea here was to look
als like
f
=
(
y
1
+
z
1
)...(
y
n
+
z
n
)
with
(
f
)
=
,
Z
[
Raz
]
Y
at
for a
random partition
, and show that with high probability the rank of
the partial derivative matrix is far from full. As a toy example, we shall see why this
has the potential to give lower bounds for depth-3 multilinear circuits.
(
f
)
,
Z
Lemma 28
Let f
(
X
)
=
1
...
d
be an n-variate multilinear polynomial. If X
=
Y
∈
Z is a random partition with
|
Y
|=|
Z
|=|
X
|
/
2
, then with high probability we
have
[
Raz
]
Y
2
|
X
|
/
2
2
−|
X
|
/
16
(
f
)
≥
·
.
,
Z
It is to be noted that we should expect a random polynomial to be full-rank with
respect to any partition, so the measure
[
Raz
]
Y
is expected to be 2
|
X
|
/
2
which
(
)
f
,
Z
should yield a lower bound of 2
ˇ(
|
X
|
)
.
i
depends on
Sketch of Proof
Without loss of generality we can assume that each
at least two variables as removing the
i
's that depend on just one variable does not
[
Raz
]
Y
(
)
|
|=
alter
f
with respect to any partition. Let
X
n
.
,
Z
[
Raz
]
Y
2
d
and hence if
d
Using Observation 26,
(
f
)
≥
<
n
/
3 then we are done.
,
Z
Hence assume that
d
ↆ
n
/
3. By a simple averaging argument, there must hence be
at least
d
/
4ofthe
i
's that depend on at most 3 variables; we shall refer to these as
the
small
i
's.
Since the partition is chosen at random, on expectation a quarter of the small
i
's would have all its variables mapped to either
Y
or
Z
, hence not contributing to
[
Raz
]
Y
(
)
f
. Therefore, with high probability,
,
Z
