Information Technology Reference
In-Depth Information
LEMMA
10.11.2
Let
g
:
A
m
that is either a subfunction
or a reduction obtained by restricting
f
to a subset of its domain. A lower bound to the space-time
product
ST
on branching programs for
g
is also a lower bound for
f
.
r
→A
s
be a reduction of
f
:
A
n
→A
Proof
Given any branching program for
f
, we can construct one for
g
that has no more
vertices or longer paths as follows. If
g
is obtained by deleting outputs, delete these outputs
from vertices in the branching program. This may allow the coalescing of vertices. If
g
is
obtained by restricting the set of values that variables of
f
can assume, this may make some
paths and subgraphs inaccessible and therefore removable. If
g
is obtained by giving two
variables of
f
the same identity, this constrains the branching program and again may make
some subgraphs inaccessible. In all cases neither the number of vertices nor the length of
any path to a sink vertex is increased by the reduction of
f
to
g
. Thus, any lower bound to
ST
for
g
must be a lower bound for
f
.
10.12
Properties of “nice” and “ok” Matrices*
In this section we develop properties of matrices that are
γ
-nice or
γ
-ok, concepts we now
introduce. (A matrix that is
γ
-nice is also
γ
-ok.) These properties are used in Section
10.13
to develop lower bounds on the exchange of space for time using the Borodin-Cook method.
This section requires a knowledge of probability theory.
DEFINITION
10.12.1
An
n × m
matrix
A
,
n ≤ m
,is
γ
-nice
for
0
<γ<
1
/
2
if and only if
for all
p
≤
γn
and
q
≥
n
−
γn
every
p
×
q
submatrix of
A
has rank
p
. Such a matrix is
γ
-ok
if all such
p
×
q
submatrices have rank at least
γp
.
As shown below, most matrices are
γ
-nice, a fact that is used in several places.
LEMMA
10.12.1
At least a fraction
(
1
−|A|
−
1
(
2
/
3
)
γn
)
of the
|A|
n
2
n
×
n
matrices over a
2
,are
γ
-nice for some constant
γ
,
0
<γ<
2
, independent of
n
and
A
|A| ≥
A
subset
of a field,
.
This result also holds for
n
n
Toeplitz matrices, matrices
[
t
i
,
j
]
with the property that
t
i
,
j
=
a
i−j
;
that is, all elements on each diagonal are the same.
×
Proof
Let
r
=
γn
and
s
=
n
−
r
. The proof is established by deriving upper bounds on
the number
N
(
r
,
s
)
of
r
×
s
matrices in an
n
×
n
matrix
M
and the probability
q
(
r
,
s
)
that
any particular
r
r
submatrix (it fails to have
rank
r
)wheneachentryin
M
is equally likely to be an element of
×
s
matrix fails to contain a non-singular
r
×
. Since the probability
of a union of events is at most the sum of the probabilities of the events, the probability that
some
r
A
s
matrix fails to have rank
r
is at most
q
(
r
,
s
)
N
(
r
,
s
)
.
It is straightforward to show that
×
N
(
r
,
s
)=
n
r
2
since an
r
×
s
submatrix of an
n
×
n
matrix is chosen by selecting a set of
r
rows and
asetof
s
columns and each can be chosen in
r
ways.
(Note that
s
=
r
.) We
now show that the binomial coefficient
r
is at most
(
n/r
)
r
e
r
.Weusethefactthat
n
!
/
(
n
n
r
and the observation that
r
r
/r
!
is a term in
−
r
)! =
n
(
n
−
1
)
···
(
n
−
r
+
1
)
≤
Search WWH ::
Custom Search