Information Technology Reference
In-Depth Information
[ Raz ]
Y
2 m
/
(˄(
Det n )) =
Lemma 34
With probability at least 1
100 , we have that
,
Z
n 1 / 3 .
where ˄ is a random restriction to 2 m variables for m
=
Combining Lemma 34 with Lemma 32, we have the following theorem.
Theorem 35 [ Raz09 ] Any multilinear formula computing Det n or Perm n must be
of size n ˇ( log n ) .
5.8.3 Stronger Lower Bounds for Constant Depth Multilinear
Formulas
Looking back at Lemma 32, we see that whenever f
(
X
)
is computable by a size
[ Raz ]
Y
is exponentially smaller than 2 | X | / 2 with probabil-
s multilinear formula
(
f
)
,
Z
ity 1
| log | X | . Hence we had to settle for a n ˇ( log n ) lower bound not
because of the rank deficit but rather because of the bounds in the probability esti-
mate. Unfortunately, this lower bound technique cannot yield a better lower bound
for multilinear formulas as there are explicit examples of polynomials computable
by poly-sized multilinear circuits with
s
·|
X
[ Raz ]
Y , Z
2 | X | / 2 under every partition
[ Raz06 ]. However, the probability bound can be improved in the case of constant
depth multilinear circuits to give stronger lower bounds.
Note that Lemma 32 was proved by considering multilinear log-products (Defin-
ition 29) as the building blocks. To show that a multilinear log product g 1 (
(
f
) =
X 1 )...g
(
has small rank under a random partition, we argued that the probability that
all the X i 's are partitioned in a roughly balanced fashion is quite small. This was
essentially done by thinking of this as
X )
=
O
(
log n
)
close-to-independent events,
each with probability 1
/
poly
(
n
)
.
was much larger than log n (with other parameters being roughly the same), it
should be intuitively natural to expect a much lower probability of all the X i 's being
partitioned in a roughly balanced manner. This indeed is the case for constant depth
multilinear circuits, and we briefly sketch the key points where they differ from the
earlier proof. The first is an analog of Definition 29 in this setting.
If
Definition 36 A multilinear polynomial f is said to be a multilinear t -product if f
can be written as f
= g 1 ...g t with the following properties:
The variable sets of the g i are mutually disjoint
Each g i non-trivially depends on at least t variables
Lemma 37 Let f be a multilinear polynomial of degree d over n variables that is
computed by a depth-
multilinear formula
ʲ
of size s. Then, f can be written as
1
/
2
, and a multilinear
a sum of at most s multilinear t -products for t
= (
n
/
100
)
polynomial of degree at most n
/
100 .
Search WWH ::




Custom Search