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