Information Technology Reference
In-Depth Information
E
i
hold.
Let us go back to estimating the probability that all the events
Pr [
E
1
⃐···⃐
E
t
]
=
Pr
[
E
1
]·
Pr
[
E
2
|
E
1
]···
Pr
[
E
t
|
E
1
⃐···⃐
E
t
−
1
]
.
The event
E
1
is just the probability that a random set
Y
of size
|
X
|
/
2 intersects
X
1
k
. This is just a particular setting of the
hypergeometric distribution and Lemma 31 asserts that
|
X
i
|
2
,
|
X
i
|
2
in
t
places where
t
∗
−
k
−
O
⊣
2
k
⊤
Pr
[
E
1
]≥
∀
|
.
X
|
To apply a similar bound for the other terms, consider the event
E
i
given that
E
1
,...,E
i
−
1
hold. Let
X
and
Y
X
. The fact
=
X
\
(
X
1
∃
...
∃
X
i
−
1
)
=
Y
ₔ
that
E
1
,...,E
i
−
1
hold means that the partition has been fairly balanced in the first
Y
|≥|
X
|+
(
ik
. Hence, we would still be in the range of
parameters in Lemma 31 to also get that
i
−
1
)
parts and hence
|
O
⊣
2
k
⊤
t
∞
i
≥
Pr
[
E
i
|
E
1
⃐···⃐
E
i
−
1
]≥
∀
|
X
|
|
−
∂
log
|
X
|
=
Pr [
E
1
⃐···⃐
E
t
]
≥ |
X
for some
∂ >
0
Pr
20
1
/
[
Raz
]
Y
2
(
|
X
|
/
2
)
−|
X
|
|
−
∂
log
|
X
|
.
=
(g
1
...g
t
)
≥
≥ |
X
,
Z
Hence, if
g
1
...g
t
is a log-product multilinear polynomial, then with probability
at least
1
|
−
∂
log
|
X
|
we have that
[
Raz
]
Y
1
/
20
2
(
|
X
|
/
2
)
−|
X
|
. Further,
if
f
is computable by a multilinear formula of size
s
then, by Lemma 30,
f
can
be written as a sum of
−|
X
(g
1
...g
t
)
≥
,
Z
(
s
+
1
)
log-product multilinear polynomials. Hence, with
probability at least
1
|
−
∂
log
|
X
|
we have that
−
(
s
+
1
)
|
X
1
/
20
[
Raz
]
Y
2
(
|
X
|
/
2
)
−|
X
|
(
f
)
≥
(
s
+
1
)
·
.
,
Z
|
(∂/
2
)
log
|
X
|
, then with high probability a random partition
Hence, if
(
s
+
1
)<
|
X
[
Raz
]
Y
2
|
X
|
/
2
. Let us record this as a lemma.
would ensure
(
f
)
⃒
,
Z
Lemma 32
Let
f
∗ F[
X
]
be computed by a multilinear formula of size s
<
|
(∂/
2
)
log
|
X
|
|
X
for a small enough constant
∂ >
0
. Then with probability at least
|
−
(∂/
2
)
log
|
X
|
)
(
1
−|
X
we have
1
/
20
[
Raz
]
Y
2
|
X
|
/
2
2
−|
X
|
(
f
)
≥
(
s
+
1
)
·
·
,
Z
for a random partition X
=
Y
∈
Z with
|
Y
|=|
Z
|=|
X
|
/
2
.
