Information Technology Reference
In-Depth Information
We now give a proof of Proposition 23.
Proof of Proposition 23
We shall fix random values to the first row of
A
. Then,
P
A
[
Det
n
(
A
)
=
0
]≥
Pr
[
a
11
M
1
+···+
a
1
n
M
n
=
0
|
some
a
1
i
nonzero
]
+
Pr
[
a
11
= ··· =
a
1
n
=
0
]
=
Pr
[
a
11
M
1
+···+
a
1
n
M
n
=
0
|
some
a
1
i
nonzero
]
1
q
n
.
+
Whenever there is some
a
1
i
that is nonzero, then
a
11
M
1
+···+
a
1
n
M
n
is a nonzero
linear combination of minors. By a similar argument as in the proof of Lemma 22,
we have that
Pr
[
a
11
M
1
+···+
a
1
n
M
n
=
0
|
not all
a
1
i
are zero
]≥
Pr
[
Det
n
−
1
(
A
)
=
0
]
.
Unfolding this recursion, we have
1
q
+
1
q
2
+···+
1
q
n
1
[
Det
n
(
)
=
]≥
=
Pr
A
0
−
q
1
⊣
1
⊤
1
q
−
2
=
Pr
[
Det
n
(
A
)
∅=
0
]ↆ
−
=
1
.
∈
q
−
1
q
−
5.7.4 Putting It All Together
Hence, if
Det
n
is computed by a depth-3 circuit of top fan-in
s
over
F
, then
⊣
n
k
⊤
2
⊦
q
ʳ
n
s
·
=
ˇ
2
2
H
(˕)
·
n
=
ˇ
=
log
s
=
ˇ((
2
H
(˕)
−
ʳ
log
q
)
n
)
q
−
q
/
2
, we can find
a
ʳ
such that
q
˕ < ʳ
(which was required in Sect.
5.7.2
) and 2
H
is the binary entropy function.
6
By choosing
˕ <
where
H
(˕)
(˕)>ʳ
log
q
,
yielding the lower bound
def
=−
˕
log
2
(˕)
−
(
6
The binary entropy function is defined as
H
(˕)
1
−
˕)
log
2
(
1
−
˕)
.Itiswell
known that
k
≈
2
nH
(
k
/
n
)
.
