arXiv:1610.01199v4 [cs.CC] 9 Apr 2017
Targeted Pseudorandom Generators, Simulation Advice Gene
rators,
and Derandomizing Logspace
William M. Hoza
∗
Chris Umans
†
April 11, 2017
Abstract
Assume that for every derandomization result for logspace algorit
hms, there is a pseudo-
random generator strong enough to nearly recover the derando
mization by iterating over all
seeds and taking a majority vote. We prove under a precise version
of this assumption that
BPL
⊆
⋂
α>
0
DSPACE
(log
1+
α
n
).
We strengthen the theorem to an equivalence by considering two ge
neralizations of the
concept of a pseudorandom generator against logspace. A
targeted pseudorandom generator
against logspace takes as input a short uniform random seed
and
a finite automaton; it outputs
a long bitstring that looks random to that particular automaton. A
simulation advice generator
for logspace stretches a small uniform random seed into a long advic
e string; the requirement
is that there is some logspace algorithm that, given a finite automato
n and this advice string,
simulates the automaton reading a long uniform random input. We pro
ve that
⋂
α>
0
promise
-
BPSPACE
(log
1+
α
n
) =
⋂
α>
0
promise
-
DSPACE
(log
1+
α
n
)
if and only if for every targeted pseudorandom generator against
logspace, there is a simulation
advice generator for logspace with similar parameters.
Finally, we observe that in a certain
uniform
setting (namely, if we only worry about se-
quences of automata that can be generated in logspace), target
ed pseudorandom generators
against logspace
can
be transformed into simulation advice generators with similar parame
ters.
1 Introduction
1.1 Derandomization vs. pseudorandom generators
The
derandomization
program of complexity theory consists of trying to determin
istically simulate
whole classes of randomized algorithms without significant
loss in efficiency. For example, we would
like to prove that
P
=
BPP
,
NP
=
AM
, and
L
=
BPL
. The main strategy for derandomization
is to design an efficient
pseudorandom generator
. A natural question is whether this strategy is
without loss of generality. That is, does derandomization a
lways imply a pseudorandom generator
that is strong enough to recover that very same derandomizat
ion? This question appears to have
∗
Department of Computer Science, University of Texas at Aust
in,
whoza@utexas.edu
. This research was mostly
conducted while the author was an undergraduate student at t
he California Institute of Technology.
†
Department
of
Computing
and
Mathematical
Sciences,
Califo
rnia
Institute
of
Technology,
umans@cms.caltech.edu
1
first been investigated by Fortnow [For01], who gave an oracl
e separation between pseudorandom
generators and derandomization in the
P
vs.
BPP
setting.
Nevertheless, for both
NP
vs.
AM
and
P
vs.
BPP
, there are indeed known constructions
of pseudorandom generators from derandomization assumpti
ons. Most such constructions come
from the
hardness vs. randomness
paradigm. The idea is to show that derandomization assump-
tions imply
hardness
results (such as circuit lower bounds). There is a large body
of literature
[Yao82, BM84, NW94, IW97, IW98, HILL99, KvM02, Uma03] showi
ng how, in turn, to construct
pseudorandom generators from hardness. Typically, the con
structed pseudorandom generator is not
strong enough to recover the original derandomization assu
mption (e.g. [IKW02, KI04, AGHK11,
KvMS12, Wil13]) but some results are known that establish ex
act equivalence between certain
sorts of derandomizations and certain sorts of pseudorando
m generators (see [AvM12]). Goldreich
has followed another approach [Gol11a, Gol11b] to construc
t pseudorandom generators from deran-
domization assumptions in the
BPP
setting. His approach does not directly involve establishi
ng
hardness results on the way; instead, he shows how to derando
mize the standard nonconstructive
existence proof for pseudorandom generators by a reduction
to decision problems.
The subject of this paper is
L
vs.
BPL
. In this setting, there are no known constructions
of pseudorandom generators from generic derandomization a
ssumptions. Further, the question of
whether derandomization is equivalent to pseudorandom gen
erators is especially well-motivated in
this setting, because nontrivial derandomizations and pse
udorandom generators have been uncon-
ditionally constructed – and there is a significant
gap
. Iterating over all seeds of the best known
pseudorandom generator, by Nisan [Nis92b], merely proves t
hat
BPL
⊆
DSPACE
(log
2
n
) (which
can also be proven by recursive matrix exponentiation). But
the best known derandomization, the
celebrated Saks-Zhou theorem [SZ99], states that
BPL
⊆
DSPACE
(log
3
/
2
n
).
In this work, we show that (informally)
if
for every derandomization of logspace algorithms,
there is a pseudorandom generator strong enough to nearly re
cover the derandomization by it-
erating over all seeds, then
BPL
⊆
⋂
α>
0
DSPACE
(log
1+
α
n
). So establishing the
equivalence
of derandomization and pseudorandom generators
would itself
yield a strong derandomization of
BPL
.
Our result can be viewed pessimistically as showing that it w
ill be challenging to establish
equivalence of derandomization and pseudorandom generato
rs in the
BPL
setting. But it can also
be viewed optimistically as giving a
road map
for proving that
BPL
⊆
⋂
α>
0
DSPACE
(log
1+
α
n
).
From this second viewpoint, our result should be compared to
other known results that give inter-
esting sufficient conditions for derandomizing logspace:
•
Klivans and van Melkebeek showed [KvM02] that if some langua
ge in
DSPACE
(
n
) requires
branching programs of size 2
Ω(
n
)
, then there is a pseudorandom generator strong enough to
prove
L
=
BPL
. While interesting, this result does not seem to provide a vi
able road map
for derandomizing logspace, because the strong hardness as
sumption seems to be far beyond
current understanding.
•
Reingold, Trevisan, and Vadhan showed [RTV06] that if there
is an efficient pseudorandom
walk generator for
regular
digraphs, then
L
=
RL
. This result
can
be reasonably thought of
as giving a road map for derandomizing logspace; the result i
s particularly tantalizing because
in the same work, they actually
did
construct a pseudorandom walk generator for
consistently
labeled
regular digraphs. Alas, in the decade since these results we
re announced, nobody has
been able to close the gap.
2
Ordinary
pseudorandom
generator
Simulator
Targeted
pseudorandom
generator
Simulation
advice
generator
Figure 1: The four types of derandomization that we consider
. A solid arrow from
A
to
B
indi-
cates that a derandomization of type
A
trivially implies a derandomization of type
B
. Our main
result is that the implication indicated by the dashed arrow
is equivalent to the statement that
⋂
α>
0
promise
-
BPSPACE
(log
1+
α
n
) =
⋂
α>
0
promise
-
DSPACE
(log
1+
α
n
).
We view our result as promising, considering that there are a
lready established techniques for
proving equivalence of derandomization and pseudorandom g
enerators. We consider it conceivable
that those techniques can be “ported” to the
L
vs.
BPL
setting. The previously mentioned result
of [KvM02] may be a first step in that direction. To put it anoth
er way, for decades, researchers have
been trying to design strong pseudorandom generators for
BPL
; our result shows that researchers
can feel free to
make derandomization assumptions
while trying to design those pseudorandom
generators, which could make the task significantly easier.
1.2 Four types of derandomization
In fact, our main result is considerably stronger than what w
e have said so far. To explicate our
main result, it is useful to distinguish between
four
types of derandomizations of logspace. (See
Figure 1.) First, the most generic type of derandomization i
s a
simulator
for logspace. This is
an algorithm that takes as input a finite automaton
Q
, a start state
q
, and a short uniform seed
x
; it outputs a state
Sim
(
Q, q, x
) whose distribution is close to the distribution of final sta
tes that
Q
would be in were it to read a long uniform random string. (Fini
te automata provide a simple
nonuniform model of space-bounded computation; each state
of a
w
-state automaton corresponds
to a configuration of a (log
w
)-space Turing machine.)
The second type of derandomization, which should be familia
r, is a
pseudorandom generator
against logspace. A pseudorandom generator has two key feat
ures that distinguish it from a generic
simulator:
•
Input. The pseudorandom generator does not get to see the “so
urce code” of the algorithm
being simulated, i.e. it does not get (
Q, q
) as part of its input.
3
•
Output. The pseudorandom generator produces a long string f
or the automaton to read,
whereas a simulator merely produces the final state of the aut
omaton.
The third and fourth types of derandomization that we will co
nsider generalize the concept of a
pseudorandom generator by relaxing these two features resp
ectively. The third type of derandom-
ization, a
targeted pseudorandom generator
, gets as input a finite automaton
Q
, a start state
q
, and
a short uniform seed
x
; it outputs a long bitstring
Gen
(
Q, q, x
) that looks random to that particular
automaton
Q
when it starts in that particular state
q
. (Goldreich [Gol11b] coined the term “tar-
geted pseudorandom generator” in the context of
P
vs.
BPP
, where the generator gets a Boolean
circuit as its auxiliary input. In the
L
vs.
BPL
setting, targeted pseudorandom generators have
been studied before; see e.g. [Nis92a, RR99].) The fourth ty
pe of derandomization, a
simulation
advice generator
, stretches a short uniform seed
x
into a long advice string
Gen
(
x
); the requirement
is that there is a deterministic logspace algorithm
S
such that
Sim
(
Q, q, x
)
def
=
S
(
Q, q,
Gen
(
x
)) is a
simulator for logspace. To the best of our knowledge, we are t
he first to study simulation advice
generators.
Our main result is that
⋂
α>
0
promise
-
BPSPACE
(log
1+
α
n
) =
⋂
α>
0
promise
-
DSPACE
(log
1+
α
n
)
(1)
if and only if for every targeted pseudorandom generator aga
inst logspace, there is a simula-
tion advice generator with similar parameters. (The precis
e statement is in Section 2.) Here,
promise
-
BPSPACE
(
s
(
n
)) is the set of promise problems decidable by probabilistic
space-
s
(
n
)
Turing machines that always halt and that have error probabi
lity at most 1
/
3;
promise
-
DSPACE
(
s
(
n
))
is its deterministic analog.
Additionally, in Section 7, we observe that targeted pseudo
random generators against logspace
can
be transformed into simulation advice generators for logsp
ace if we move to the
uniform setting
,
i.e. we only worry about sequences of automata that can be gen
erated in logspace. This is almost
immediate from the definitions, but it illustrates how much e
asier it is to construct simulation
advice generators than it is to construct pseudorandom gene
rators.
1.3 Proof techniques
One direction of our main result is easy. Under the assumptio
n that Equation 1 holds, simulation
advice generators are uninteresting objects that can be con
structed for trivial reasons. The main
content of the theorem is the reverse direction.
The proof of the harder direction is by extending the techniq
ues of Saks and Zhou [SZ99]. The
way Saks and Zhou originally presented their result is that t
hey used specific properties of Nisan’s
pseudorandom generator [Nis92b] to design a space-efficient
algorithm for approximate matrix
exponentiation by reusing parts of the seed. Later, Armoni [
Arm98] constructed a pseudorandom
generator that is better than Nisan’s for fooling low-rando
mness algorithms, and using Zuckerman’s
oblivious sampler [Zuc97], he adapted the Saks-Zhou algori
thm to use his generator instead of
Nisan’s, giving a better derandomization of such algorithm
s.
In Section 4, we show that with Armoni’s ideas, the Saks-Zhou
construction can instead be
formulated as a
transformation on simulators.
Roughly: Starting from a simulator that uses an
s
-bit seed to simulate
m
0
steps of a
w
-state automaton, given a parameter
m
, the Saks-Zhou-
Armoni (SZA) transformation produces a new simulator that u
ses an
O
(
s
+
(log
m
)(log
w
)
log
m
0
)
-bit seed
4
to simulate
m
steps of a
w
-state automaton. We consider this reformulation to be inte
resting in its
own right, as it clarifies the power of Saks-Zhou rounding.
A simple, tempting idea is to start with a weak simulator and a
pply the SZA transformation
t
times for some large constant
t
. In iteration
i
, choose
m
= 2
log
i/t
w
. Then we end up with a
simulator with
m
=
w
(large enough to simulate randomized space-bounded algori
thms), and the
seed length is only
O
(log
1+1
/t
w
)! But unfortunately, the space complexity blows up with eac
h
application of the SZA transformation.
Because of the recursive structure of the SZA transformatio
n, the blowup can be avoided as long
as the SZA transformation is only applied to simulators obta
ined from simulation advice generators.
So to prove the harder direction of our main result, we cycle b
etween three transformations:
1. Our assumption, which transforms a targeted pseudorando
m generator into a simulation
advice generator. (This “transformation” is not necessari
ly effective.)
2. The SZA transformation, which we now think of as transform
ing a simulation advice generator
into a simulator.
3. A simple transformation based on the method of conditiona
l probabilities, which transforms
a simulator into a targeted pseudorandom generator.
The SZA transformation substantially increases the number
of steps being simulated. For each
of the three transformations, we incur only mild degradatio
n in the seed length, space com-
plexity, etc. Hence, overall, each cycle significantly incr
eases the output length of our targeted
pseudorandom generator without degrading the other parame
ters too much. By iterating the
cycle a large constant number of times, we end up with a genera
tor strong enough to collapse
⋂
α>
0
promise
-
BPSPACE
(log
1+
α
n
) to
⋂
α>
0
promise
-
DSPACE
(log
1+
α
n
).
2 Formal statement of main result
Let [
w
] denote the set
{
1
,
2
, . . . , w
}
. Let
U
n
denote the uniform distribution on
{
0
,
1
}
n
. For two
probability distributions
μ, μ
′
on the same measurable space, write
μ
∼
ε
μ
′
to mean that the total
variation distance between
μ
and
μ
′
is at most
ε
.
Definition 1.
If
A
is a set of functions
{
0
,
1
}
m
→
[
w
], we say that a function
Sim
:
A
×{
0
,
1
}
s
→
[
w
]
is an
ε
-simulator
for
A
if for every
f
∈
A
, we have
Sim
(
f, U
s
)
∼
ε
f
(
U
m
).
Definition 2.
If
A
is a set of functions
{
0
,
1
}
m
→
[
w
], we say that a function
Gen
:
A
× {
0
,
1
}
s
→
{
0
,
1
}
m
is a
targeted
ε
-pseudorandom generator
against
A
if the function
Sim
(
f, x
)
def
=
f
(
Gen
(
f, x
))
is an
ε
-simulator for
A
.
The standard definition of a pseudorandom generator is the sp
ecial case where
Gen
(
f, x
) does
not depend on
f
.
Definition 3.
A (
w, d
)
-automaton
is a function
Q
: [
w
]
×{
0
,
1
}
d
→
[
w
]. If
Q
1
is a (
w, d
1
)-automaton
and
Q
2
is a (
w, d
2
)-automaton, then
Q
2
Q
1
is the (
w, d
1
+
d
2
)-automaton defined by
(
Q
2
Q
1
)(
q
;
x, y
) =
Q
2
(
Q
1
(
q
;
x
);
y
)
.
Let
Q
m
w,d
be the set of all functions
{
0
,
1
}
md
→
[
w
] of the form
x
7→
Q
m
(
q
;
x
) where
Q
is a
(
w, d
)-automaton.
5
Parameter
Interpretation
w
Number of states in the automaton
d
Number of bits the automaton reads in each step
m
Number of steps the automaton takes
ε
Simulation error, in total variation distance
s
Seed length
a
Number of advice bits
Figure 2: A summary of the parameters of the targeted pseudor
andom generators, simulation
advice generators, and simulators that we study. Each famil
y of generators/simulators is indexed
by
w
, and the other parameters are functions of
w
.
In words,
Q
m
w,d
is the set of functions computed by letting a (
w, d
)-automaton run for
m
steps
and observing its final state. An element of
Q
m
w,d
can be specified by a pair (
Q, q
), and this is how it
will be presented to simulators and targeted pseudorandom g
enerators in our theorem statements.
Definition 4.
Suppose that for each
w
,
Gen
w
:
{
0
,
1
}
s
→ {
0
,
1
}
a
is a function, and
A
w
⊆
Q
m
w,d
,
where
s, a, d, m
are functions of
w
. We say that
Gen
w
is
1
an
ε
-simulation advice generator for
A
w
if there is some deterministic logspace algorithm
S
such that the function
Sim
(
Q, q, x
)
def
=
S
(
Q, q,
Gen
w
(
x
)) is an
ε
-simulator for
A
w
.
Note that
S
’s space bound is logarithmic in terms of its input length, i.
e. it may use
O
(
d
+
log
w
+ log
a
) bits of space. It is desirable for
m
to be
big
and
s, a, ε
to be
small
. E.g. as long as
a
≤
poly(
w,
2
d
), it contributes nothing to the asymptotic space complexit
y of
S
. To explicate the
definition, we give several examples of where simulation adv
ice generators might come from:
1. Any (standard, non-targeted)
ε
-pseudorandom generator
Gen
w
against
Q
m
w,d
is also an
ε
-
simulation advice generator for
Q
m
w,d
. The associated algorithm
S
(
Q, q, y
) computes
Q
m
(
q
;
y
)
where
y
is the output of
Gen
w
. This can be done in logspace by storing the current state of
Q
and the current
d
-bit chunk of
y
.
2. Suppose there is some logspace
ε
-simulator for
Q
m
w,d
with seed length
s
. Then the identity
function on
{
0
,
1
}
s
is an
ε
-simulation advice generator for
Q
m
w,d
. (So under the assumption that
promise
-
L
=
promise
-
BPL
, simulation advice generators are only interesting for ext
reme
values of parameters.)
3. Suppose
Gen
w
is a targeted
ε
-pseudorandom generator against
Q
m
w,d
of the form
Gen
w
(
Q, q, x
) =
G
(
Compress
(
Q, q, x
)
, x
), where
Compress
is computable in
O
(
d
+ log
w
) space and outputs
b
bits. Let
Gen
′
w
(
x
) be
x
concatenated with the truth table
T
of
G
(
·
, x
). Then
Gen
′
w
is an
ε
-simulation advice generator for
Q
m
w,d
with output length
a
=
s
+
m
2
b
. The associated algo-
rithm
S
(
Q, q, x, T
) computes
c
=
Compress
(
Q, q, x
), referring to its advice tape for access to
x
. Then,
S
looks up the value
y
=
G
(
c, x
) in the
T
portion of its advice tape and computes
Q
m
(
q
;
y
).
1
Strictly speaking, this is a property of the family
{
Gen
w
}
, not of the individual function. There should be just
one
S
for the whole family, and
ε
is a function of
w
.
6
4. Suppose
Sim
is an
ε
-simulator for
Q
m
w,d
that perhaps uses much more than logspace, but that,
each time it reads from
Q
or
q
, first
erases
all but
O
(
d
+ log
w
) bits. If
c
is a configuration
of
Sim
(
Q, q, x
) in which
Sim
just read from
Q
or
q
, then let
f
(
c, x
) be the configuration that
Sim
(
Q, q, x
) will next be in when it is about to read from
Q
or
q
. Let
Gen
w
(
x
) be the truth
table of
f
(
·
, x
). Then
Gen
w
is an
ε
-simulation advice generator for
Q
m
w,d
with output length
a
≤
poly(
w,
2
d
). The associated algorithm
S
(
Q, q,
Gen
w
(
x
)) simulates
Sim
(
Q, q, x
). To update
the simulation’s configuration,
S
alternates between reading a bit from (
Q, q
) and using its
advice tape.
Suppose
{
F
w
}
is a family where
F
w
is a simulator for, a simulation advice generator for, or a
targeted pseudorandom generator against
Q
m
w,d
, with seed length
s
(
w
). For convenience, we will
say that the family is
efficiently computable
if
s
(
w
) is space constructible and given (
w, X
),
F
w
(
X
)
can be computed in deterministic space
O
(
s
(
w
)). We will often speak of an individual function
F
w
being efficiently computable when the family is clear.
We now formally state our main result. In Condition 2,
η, σ, μ
are the parameters of the targeted
pseudorandom generator. The last parameter
γ
quantifies the extent to which the derandomization
degrades when the targeted pseudorandom generator is repla
ced with a simulation advice generator.
Theorem 1.
The following are equivalent.
1.
⋂
α>
0
promise
-
BPSPACE
(log
1+
α
n
) =
⋂
α>
0
promise
-
DSPACE
(log
1+
α
n
)
.
2. For any constant
μ
∈
[0
,
1]
, for any sufficiently small constants
σ > η >
0
, and for any
constant
γ >
0
, the following holds. Suppose there is a family
{
Gen
w
}
, where
Gen
w
is an
efficiently computable targeted
ε
-pseudorandom generator against
Q
m
w,
1
with seed length
s
,
satisfying
s
≤
O
(log
1+
σ
w
)
,
log(1
/ε
) = log
1+
η
w,
log
m
≥
log
μ
w.
Then there is another family
{
Gen
′
w
}
, where
Gen
′
w
is an efficiently computable
ε
′
-simulation
advice generator for
Q
m
′
w,
1
with seed length
s
′
and output length
a
′
, satisfying
s
′
≤
O
(log
1+
σ
+
γ
w
)
,
log(1
/ε
′
) = log
1+
η
−
γ
w,
log
m
′
≥
log
μ
−
γ
w,
log
a
′
≤
O
(log
1+
η
+
γ
w
)
.
3 The implicit oracle model
Toward proving Theorem 1, we introduce a model of space-boun
ded oracle algorithms that seem-
ingly does not appear in the literature. Our new oracle model
(the “implicit oracle model”) gives a
convenient framework for expressing the SZA result as a tran
sformation on simulators and clarifies
the effect on the simulator’s space complexity when the SZA tra
nsformation is iterated.
The implicit oracle model is similar to Wilson’s oracle stac
k model [Wil88], and it is appropriate
for the situation where the algorithm doesn’t have room to wr
ite down the entire query string, but
it is ready to provide the oracle with random access to the que
ry string (possibly by making more
oracle queries.)
7
Definition 5.
Fix a set
A
⊆ {
0
,
1
}
∗
. Giving an algorithm
implicit oracle access
to
A
allows the
algorithm to interface with an oracle in the following ways:
•
The algorithm can
invoke
the oracle, which passes control to the oracle.
•
The oracle can
read position
j
∈
N
by giving
j
to the algorithm. This passes control back to
the algorithm. We associate this read with the most recent un
resolved invocation.
•
The algorithm can give the oracle a
query value
b
∈ {
0
,
1
,
⊥}
. This passes control back to the
oracle and
resolves
the most recent unresolved read.
•
The oracle can give the algorithm a boolean
answer value
. This passes control back to the
algorithm and
resolves
the most recent unresolved invocation.
The oracle is guaranteed to behave as follows: Fix any
x
∈ {
0
,
1
}
∗
. Suppose that for some invocation,
when the oracle reads position
j
, the algorithm specifies value
x
j
(where we interpret
x
j
=
⊥
for
j >
|
x
|
.) Then the oracle will make finitely many reads and give the an
swer value corresponding
to whether
x
∈
A
, and every read will be of a position
j
≤ |
x
|
+ 1.
We extend the definition by saying that we give an algorithm im
plicit oracle access to a
function
f
:
{
0
,
1
}
∗
→ {
0
,
1
}
∗
to mean that we give the algorithm implicit oracle access to t
he set
A
=
{
(
x, b,
0) :
|
f
(
x
)
| ≤
b
} ∪ {
(
x, b,
1) :
f
(
x
)
b
= 1
}
.
Wilson’s oracle stack model is equivalent to the implicit or
acle model with the additional re-
striction that the oracle is guaranteed to read its input fro
m left to right.
Ultimately, we will only use the implicit oracle model in int
ermediate steps of our proof; for our
final algorithm, we will “plug in” actual algorithms in place
of the oracle. The next lemma says
what happens to space complexity when this actual algorithm
is plugged in.
Lemma 1.
Suppose
Gen
:
{
0
,
1
}
s
→ {
0
,
1
}
a
is an efficiently computable
ε
-simulation advice gen-
erator for
Q
m
w,d
, and let
Sim
be the corresponding simulator. Suppose
Alg
is an implicit oracle
algorithm and
x
is an input such that during the execution of
Alg
Sim
(
w, x
)
,
Alg
uses
s
′
bits of space,
and at any moment, there are at most
u
unresolved oracle invocations, and there are at most
v
unresolved reads of seeds. Then
Alg
Sim
(
w, x
)
can be computed (by a non-oracle algorithm) in space
O
(
s
′
+
s
·
(
v
+ 1) +
u
·
(
d
+ log
w
+ log
a
))
.
Proof.
Recall that
Sim
is of the form
Sim
(
Q, q, x
) =
S
(
Q, q,
Gen
(
x
)). Naturally, just simulate
Alg
,
replacing its oracle queries with computations of
Sim
. The space needed is
s
′
for the computation
of
Alg
, plus
O
(
d
+ log
w
+ log
a
) for each unresolved execution of
S
, plus
O
(
s
) for each unresolved
execution of
Gen
. The number of unresolved executions of
S
is precisely
u
. The number of unresolved
executions of
Gen
is at most
v
+ 1, because while an instance of
Sim
is in the process of computing
Gen
, that instance never queries the (
Q, q
) portion of its input.
4 The SZA transformation
Formulating the Saks-Zhou construction as a transformatio
n on simulators is not technically chal-
lenging. A (
w, d
)
-automaton with fail state
2
is a (
w
+1
, d
)-automaton such that
Q
(
w
+1;
y
) =
w
+1
2
This is equivalent to the definition of a “finite state machine
of type (
w, d
)” in [SZ99] or that of a “(
w, d
)-
automaton” in [CCvM06].
8
for all
y
. (We think of
w
+ 1 as the “fail state”.) Let
̃
Q
m
w,d
be the set of all functions of the form
x
7→
Q
m
(
q
;
x
) where
Q
is a (
w, d
)-automaton with fail state. When we give an algorithm (impl
icit)
oracle access to an
ε
-simulator for
̃
Q
m
w,d
with seed length
s
, it is understood that the algorithm can
query for the parameters
w, d, m, ε, s
as well as interacting with the oracle in the usual way.
Theorem 2.
There is a constant
c
∈
N
and a deterministic implicit oracle algorithm
SZA
with the
following properties. Pick
w
∈
N
, ε >
0
and let
d
=
⌈
c
log(
w/ε
)
⌉
. Suppose
Sim
is an
ε
-simulator
for
̃
Q
m
0
w,d
with seed length
s
≤
m
0
≤
w
. Then
1. For any
m
∈
N
, there is some
m
′
≥
m
such that
SZA
Sim
m
is a
(12
mε
)
-simulator for
̃
Q
m
′
w,d
.
(Here
m
is an input to
SZA
; we write it as a subscript merely to separate it from the usua
l
simulator inputs.)
2. At any moment in the execution of
SZA
Sim
m
, there are at most
u
def
=
⌈
(log
m
)
/
(log
m
0
)
⌉
unre-
solved oracle invocations, and there is at most one unresolv
ed read of the seed of
Sim
.
3. The seed length and space complexity of
SZA
Sim
m
are both
O
(
s
+
u
log(
w/ε
))
.
To illustrate the theorem statement, we demonstrate how to r
ecover the original Saks-Zhou
result of [SZ99]. Let
Gen
:
{
0
,
1
}
s
→ {
0
,
1
}
m
0
be the (non-targeted) efficiently computable
ε
-
pseudorandom generator against
̃
Q
m
0
w,d
of [INW94, Theorem 3] with
m
0
= 2
√
log
w
,
ε
= 1
/
(6
·
12
w
),
and
s
≤
O
(log
3
/
2
w
). Let
Sim
be the corresponding simulator. Then
SZA
Sim
w
is a (1
/
6)-simulator
for
̃
Q
m
′
w,d
for some
m
′
≥
w
, and hence it can be used to simulate
BPL
(by ensuring that all
transitions from the halting configurations are self loops.
) The parameter
u
is
O
(
√
log
w
), and
hence the seed length and space usage of
SZA
Sim
w
are both
O
(log
3
/
2
w
). By Lemma 1, the space
needed to simulate
SZA
Sim
w
by a non-oracle algorithm is
O
(log
3
/
2
w
). Iterating over all seeds proves
BPL
⊆
DSPACE
(log
3
/
2
n
), since the number of configurations of a logspace Turing mac
hine on
a length
n
input is
w
≤
poly(
n
).
The rest of this section is the proof of Theorem 2. All of the id
eas in the proof are already
present in [SZ99] and [Arm98]. Our main contributions in thi
s section are the
formulation and
statement
of Theorem 2, which enable us to derive the consequence expre
ssed in Theorem 1.
4.1 Randomness efficient samplers
The first step to proving Theorem 2 is an observation by Armoni
[Arm98]. Let
NisGen
denote
Nisan’s generator. Saks and Zhou used a special feature of
NisGen
. The special feature is that the
seed can be split into two parts
x, z
with
z
≤
O
(log(
w/ε
)) such that for any particular automaton
Q
, for most values of
x
,
NisGen
(
x,
·
) is a good pseudorandom generator for
Q
. (Namely, we can let
x
be the sequence of hash functions and
z
be the input to those hash functions.) Armoni observed
that
any
pseudorandom generator can be made to have this feature just
by precomposing with
an
averaging sampler
. We give here the appropriate notion of averaging samplers f
or [
w
]-valued
functions:
Definition 6.
Fix
Samp
:
{
0
,
1
}
ℓ
× {
0
,
1
}
d
→ {
0
,
1
}
s
. For a function
f
:
{
0
,
1
}
s
→
[
w
], we say that
a string
x
∈ {
0
,
1
}
ℓ
is
δ
-good for
f
if
f
(
Samp
(
x, U
d
))
∼
δ
f
(
U
s
). We say that
Samp
is an
averaging
(
δ, γ
)
-sampler for
[
w
]
-valued functions
if for every
f
:
{
0
,
1
}
s
→
[
w
],
Pr
x
∼
U
ℓ
[
x
is
δ
-good for
f
]
≥
1
−
γ.
9
We need a space-efficient averaging sampler with good paramet
ers. Armoni used Zuckerman’s
averaging sampler [Zuc97], but Zuckerman’s sampler breaks
down for extremely small values of
δ
.
Therefore, to get a slightly more general result, we use the G
UV extractor [GUV09], or rather a
space-optimized version by Kane, Nelson, and Woodruff [KNW0
8]. It is standard that extractors
are good samplers; the following lemma expresses the parame
ters achieved by the space-optimized
GUV extractor when it is viewed as a sampler for [
w
]-valued functions:
Lemma 2.
For all
s, w
∈
N
and all
δ, γ >
0
, there is an averaging
(
δ, γ
)
-sampler for
[
w
]
-valued
functions
Samp
:
{
0
,
1
}
ℓ
× {
0
,
1
}
d
→ {
0
,
1
}
s
with
ℓ
≤
O
(
s
) + log(
w/γ
)
and
d
≤
O
(log
s
+ log
w
+ log(1
/δ
) + log log(1
/γ
))
,
where
Samp
(
x, y
)
can be computed in
O
(
s
+ log(
w/γ
))
space.
Proof.
Let
ℓ
= 2
s
+ 1 + log(
w/γ
). By [KNW08, Theorem A.14], there is a (2
s,
2
δ/w
)-extractor
Samp
:
{
0
,
1
}
ℓ
× {
0
,
1
}
d
→ {
0
,
1
}
s
with
d
≤
O
(log
ℓ
+ log(
w/δ
)), which is
O
(log
s
+ log
w
+ log(1
/δ
) + log log(1
/γ
))
as claimed, such that
Samp
(
x, y
) can be computed in
O
(
ℓ
+log(
w/δ
)) space, which is
O
(
s
+log(
w/δ
))
space as claimed.
All that remains is to prove correctness. Fix
f
:
{
0
,
1
}
s
→
[
w
]. Say
x
∈ {
0
,
1
}
ℓ
is
good for
f
with respect to
z
∈
[
w
] if
|
Pr[
f
(
Samp
(
x, U
d
)) =
z
]
−
Pr[
f
(
U
s
) =
z
]
| ≤
2
δ/w.
By [Zuc97, Proposition 2.7] (or rather its proof), for each
z
∈
[
w
],
Pr
x
∼
U
ℓ
[
x
is good for
f
with respect to
z
]
≥
1
−
2
−
log(
w/γ
)
= 1
−
γ/w.
Therefore, by the union bound over the
w
different values of
z
, the probability that a uniform
random
x
is good for
f
with respect to
every
z
∈
[
w
] simultaneously is at least 1
−
γ
. For such an
x
, the
ℓ
1
distance between
f
(
Samp
(
x, U
d
)) and
f
(
U
s
) is at most 2
δ
. Total variation distance is half
ℓ
1
distance, so such an
x
is
δ
-good for
f
, completing the proof.
4.2 The snap operation
At the heart of the SZA transformation is a randomized roundi
ng operation that we will call
Snap
. This operation slightly perturbs a given automaton with fa
il state. The basic feature of this
perturbation is that if
Q
≈
Q
′
, then with high probability,
Snap
(
Q
) =
Snap
(
Q
′
). This phenomenon
(which we will make rigorous in Lemma 5) is reminiscent of “sn
apping to a grid”, hence the name.
A
substochastic
d
-matrix
is a square matrix
M
filled with nonnegative multiples of 2
−
d
such
that for every
q
,
∑
r
M
qr
≤
1. A (
w, d
)-automaton with fail state
Q
has a
transition probability
matrix
M
(
Q
), a
w
×
w
substochastic
d
-matrix defined by
M
(
Q
)
qr
= Pr
z
∈{
0
,
1
}
d
[
Q
(
q
;
z
) =
r
]
.
10
Conversely, from a
w
×
w
substochastic
d
-matrix
M
, we define a
canonical automaton with fail state
Q
(
M
) by identifying
{
0
,
1
}
d
with [2
d
] and setting
Q
(
M
)(
q
;
z
) =
{
the smallest
r
such that
z
2
−
d
≤
∑
r
r
′
=1
M
qr
′
if such an
r
exists
w
+ 1
otherwise.
Definition 7.
For
p
∈
[0
,
1] and ∆
∈
N
, define
⌊
p
⌋
∆
=
⌊
2
∆
p
⌋
2
−
∆
, i.e.
p
truncated to ∆ bits after
the radix point. Define
Snap
: [0
,
1]
× {
0
,
1
}
∗
→
[0
,
1] by
Snap
(
p, y
) =
⌊
max
{
0
, p
−
(0
.y
)
·
2
−|
y
|
}⌋
|
y
|
,
where 0
.y
represents a number in [0
,
1] in binary.
3
Extend the definition to operate on matrices
componentwise:
Snap
(
M, y
)
qr
=
Snap
(
M
qr
, y
). Further extend
Snap
to operate on automata with
fail states by the rule
Snap
(
Q, y
) =
Q
(
Snap
(
M
(
Q
)
, y
)). (The second argument to
Snap
should be
thought of as random bits.)
Let
k·k
denote the
matrix norm
, i.e. the maximum sum of absolute entries of any row. Define a
metric on automata with fail states with the same number of st
ates by setting
ρ
(
Q, Q
′
) =
kM
(
Q
)
−
M
(
Q
′
)
k
. The following lemma relates this metric to total variation
distance.
Lemma 3.
Suppose
Q
is a
(
w, d
)
-automaton with fail state and
Q
′
is a
(
w, d
′
)
-automaton with fail
state. Let
δ
be the maximum, over all
q
∈
[
w
+ 1]
, of the total variation distance between
Q
(
q
;
U
d
)
and
Q
′
(
q
;
U
d
′
)
. Then
1
2
ρ
(
Q, Q
′
)
≤
δ
≤
ρ
(
Q, Q
′
)
.
Proof.
For each
q, r
∈
[
w
+ 1], let
ρ
qr
= Pr[
Q
(
q
;
U
d
) =
r
]
−
Pr[
Q
′
(
q
;
U
d
′
) =
r
]. Then
ρ
(
Q, Q
′
) =
max
q
∈
[
w
]
∑
r
∈
[
w
]
|
ρ
qr
|
. Since total variation distance is half
L
1
distance,
δ
=
1
2
max
q
∈
[
w
+1]
∑
r
∈
[
w
+1]
|
ρ
qr
|
.
This immediately shows that
1
2
ρ
(
Q, Q
′
)
≤
δ
. For the second inequality, let
q
be such that
δ
=
1
2
∑
r
∈
[
w
+1]
|
ρ
qr
|
. Since
Q
and
Q
′
are both automata with fail states,
q
can be chosen to not be
w
+ 1, and hence
ρ
(
Q, Q
′
)
≥
∑
r
∈
[
w
]
|
ρ
qr
|
= 2
δ
− |
ρ
q,w
+1
|
. Since
∑
r
ρ
qr
= 0,
|
ρ
q,w
+1
| ≤
ρ
(
Q, Q
′
), so
ρ
(
Q, Q
′
)
≥
2
δ
−
ρ
(
Q, Q
′
). Rearranging completes the proof.
Lemma 4.
For any
(
w, d
)
-automaton with fail state
Q
and any
y
∈ {
0
,
1
}
∆
,
ρ
(
Q,
Snap
(
Q, y
))
≤
w
2
−
∆+1
.
Proof.
The snap operation perturbs each entry of the
w
×
w
matrix by at most 2
−
∆+1
.
Lemma 5.
Fix a
(
w, d
)
-automaton with fail state
Q
and let
Y
∼
U
∆
. Then
Pr[
∃
Q
′
such that
ρ
(
Q, Q
′
)
≤
2
−
2∆
and yet
Snap
(
Q, Y
)
6
=
Snap
(
Q
′
, Y
)]
≤
w
2
2
−
∆+1
.
Proof.
Let
E
qr
be the bad event that there exists
p
such that
|M
qr
−
p
| ≤
2
−
2∆
and yet
Snap
(
M
(
Q
)
qr
, Y
)
6
=
Snap
(
p, Y
). For
E
qr
to occur, there must be some
x
a multiple of 2
−
∆
such that
M
(
Q
)
qr
−
(0
.Y
)
·
2
−
∆
is in [
x
−
2
−
2∆
, x
+ 2
−
2∆
). There are only two values of
Y
that can make this happen, so
Pr[
E
qr
]
≤
2
−
∆+1
. The union bound completes the proof, since
k
M
k ≥
max
q,r
|
M
qr
|
.
3
In the notation of [SZ99] and [Arm98],
Snap
(
p, y
) =
⌊
Σ
(0
.y
)2
−|
y
|
(
p
)
⌋
|
y
|
. In the notation of [CCvM06],
Snap
(
p, y
) =
R
y,
|
y
|
(
p
).
11
4.3 The construction
Recall that
w
is the number of states (excluding the fail state),
ε
is the error of
Sim
, and
s
is
the seed length of
Sim
. Let ∆ =
⌈
log(
w
2
/ε
)
⌉
, let
δ
= 2
−
2∆
−
1
, and let
γ
= 2
ε/w
. Let
Samp
:
{
0
,
1
}
ℓ
× {
0
,
1
}
d
→ {
0
,
1
}
s
be the averaging (
δ, γ
)-sampler for [
w
]-valued functions of Lemma 2.
(This defines the constant
c
; note that Lemma 2 ensures
d
≤
O
(log(
w/ε
)), since the theorem
statement assumes
s
≤
w
.)
We now define a randomized approximate automaton powering op
eration
̂
Pow
. For a (
w, d
)-
automaton with fail state
Q
and a string
x
∈ {
0
,
1
}
ℓ
, we define a (
w, d
)-automaton with fail state
̂
Pow
(
Q, x
) by the formula
̂
Pow
(
Q, x
)(
q
;
z
) =
Sim
(
Q, q,
Samp
(
x, z
))
.
Recall that
m
0
is the number of steps simulated by
Sim
, and note that for any
Q
, for most
x
,
̂
Pow
(
Q, x
)
≈
Q
m
0
. The idea of the
SZA
transformation is to alternately apply
̂
Pow
and
Snap
. The
Snap
operation allows us to reuse the randomness of the
̂
Pow
operation from one application to the
next, thereby saving random bits.
Let
Q
0
be the (
w, d
)-automaton with fail state that is given to
SZA
as input. Recall that
u
=
⌈
(log
m
)
/
(log
m
0
)
⌉
, where
m
is the number of steps of
Q
0
that
SZA
is trying to simulate.
For a sequence
y
= (
y
1
, . . . , y
u
)
∈ {
0
,
1
}
∆
u
and a string
x
∈ {
0
,
1
}
ℓ
, we define a sequence of
(
w, d
)-automata with fail states
̂
Q
0
[
x, y
]
, . . . ,
̂
Q
u
[
x, y
] by starting with
̂
Q
0
[
x, y
] =
Q
0
and setting
̂
Q
i
+1
[
x, y
] =
Snap
(
̂
Pow
(
̂
Q
i
[
x, y
]
, x
)
, y
i
+1
)
.
(For
i
≥
1,
Q
i
is naturally thought of as a (
w,
∆)-automaton with fail state, but since ∆
≤
d
, we
can think of it as reading
d
bits for each transition and ignoring all but the first ∆ of the
m.) Finally,
for seed values
x
∈ {
0
,
1
}
ℓ
, y
∈ {
0
,
1
}
∆
u
, z
∈ {
0
,
1
}
d
, we set
SZA
Sim
m
(
Q
0
, q, x, y, z
) :=
̂
Q
u
[
x, y
](
q
;
z
)
.
4.4 Correctness
The bulk of the correctness proof consists of justifying the
fact that we use the same
x
value for
each application of
̂
Pow
in the definition of
̂
Q
i
. To do this, we define a
deterministic
approximate
powering operation
Pow
. For a (
w, d
)-automaton with fail state
Q
, define a (
w, s
)-automaton with
fail state
Pow
(
Q
) by
Pow
(
Q
)(
q
;
z
) =
Sim
(
Q, q, z
)
.
Note that
Pow
(
Q
)
≈
Q
m
0
. For a sequence
y
= (
y
1
, . . . , y
u
)
∈ {
0
,
1
}
∆
u
, define (just for the analysis)
another sequence of (
w, d
)-automata with fail states
Q
0
[
y
]
, . . . , Q
u
[
y
] by starting with
Q
0
[
y
] =
Q
0
and setting
Q
i
+1
[
y
] =
Snap
(
Pow
(
Q
i
[
y
])
, y
i
+1
)
.
We first verify that these automata
Q
i
(always) provide good approximations for the true powers
of
Q
0
:
Lemma 6.
For any
y
,
ρ
(
Q
u
[
y
]
, Q
m
u
0
0
)
≤
8
mε
.
12
Proof.
We show by induction on
i
that
ρ
(
Q
i
[
y
]
, Q
m
i
0
0
)
≤
m
i
0
−
1
m
0
−
1
·
(2
ε
+
w
2
−
∆+1
)
.
In the base case
i
= 0, this is immediate. For the inductive step, by the triangl
e inequality,
ρ
(
Q
i
+1
[
y
]
, Q
m
i
+1
0
0
)
≤
ρ
(
Q
i
+1
[
y
]
,
Pow
(
Q
i
[
y
])) +
ρ
(
Pow
(
Q
i
[
y
])
, Q
i
[
y
]
m
0
) +
ρ
(
Q
i
[
y
]
m
0
, Q
m
i
+1
0
0
)
.
The first term is at most
w
2
−
∆+1
by Lemma 4. The second term is at most 2
ε
by the simulator
guarantee and Lemma 3. The third term is at most
m
0
ρ
(
Q
i
[
y
]
, Q
m
i
0
) by [SZ99, Proposition 2.3].
Therefore, by the inductive assumption,
ρ
(
Q
i
+1
[
y
]
, Q
m
i
+1
0
0
)
≤
w
2
−
∆+1
+ 2
ε
+
m
0
·
m
i
0
−
1
m
0
−
1
·
(2
ε
+
w
2
−
∆+1
)
=
m
i
+1
0
−
1
m
0
−
1
·
(2
ε
+
w
2
−
∆+1
)
.
That completes the induction. Finally, we plug in
i
=
u
:
ρ
(
Q
u
[
y
]
, Q
m
u
0
0
)
≤
m
u
0
−
1
m
0
−
1
(2
ε
+ 2
w
2
−
∆
)
≤
2
m
·
(2
ε
+ 2
ε
)
.
Now, we show that the
Snap
operation ensures that with high probability,
̂
Q
i
and
Q
i
are exactly
equal, despite their different definitions:
Lemma 7.
Let
X
∼
U
ℓ
, Y
1
∼
U
∆
, . . . , Y
u
∼
U
∆
all be independent. Then
Pr[
there is some
i
≤
u
such that
̂
Q
i
[
X, Y
]
6
=
Q
i
[
Y
]]
≤
4
mε.
Proof.
By the sampling property, Lemma 3, and a union bound over the
w
different start states,
for each
i
∈ {
0
, . . . , u
−
1
}
,
Pr[
ρ
(
Pow
(
Q
i
[
Y
])
,
̂
Pow
(
Q
i
[
Y
]
, X
))
>
2
δ
]
≤
wγ
= 2
ε.
(2)
(Imagine picking
Y
first and then taking a probability over the randomness of
X
alone.) Now,
2
δ
= 2
−
2∆
, and by Lemma 5,
Pr
[
∃
Q
′
such that
ρ
(
Pow
(
Q
i
[
Y
])
, Q
′
)
≤
2
−
2∆
and
Snap
(
Pow
(
Q
i
[
Y
])
, Y
i
+1
)
6
=
Snap
(
Q
′
, Y
i
+1
)
]
≤
w
2
2
−
∆+1
(3)
≤
2
ε.
(4)
By the union bound over the
u
different values of
i
, the probability that
any
of these bad events
occur is at most
u
(2
ε
+ 2
ε
)
≤
4
mε
. So to prove the lemma, assume that
none
of these bad events
occur. In this case, we show by induction that
̂
Q
i
[
X, Y
] =
Q
i
[
Y
] for every 0
≤
i
≤
u
. The base
case
i
= 0 holds by definition. For the inductive step, assume
̂
Q
i
[
X, Y
] =
Q
i
[
Y
]. Then because we
assumed that the bad event of Equation 2 did not occur,
ρ
(
̂
Pow
(
̂
Q
i
[
X, Y
]
, X
)
,
Pow
(
̂
Q
i
[
Y
]))
≤
2
−
2∆
.
And hence because we assumed that the bad event of Equation 3 a
lso did not occur, we may
conclude that
Snap
(
̂
Pow
(
̂
Q
i
[
X, Y
]
, X
)
, Y
i
+1
) =
Snap
(
Pow
(
Q
i
[
Y
])
, Y
i
+1
)
.
By definition, this implies that
̂
Q
i
+1
[
X, Y
] =
Q
i
+1
[
Y
].
13
We have shown that
Q
1
, Q
2
, . . . , Q
u
provide good approximations of true powers of
Q
0
, and
with high probability,
̂
Q
i
=
Q
i
for every
i
. It immediately follows that a random transition of
̂
Q
u
gives a similar distribution as
m
u
0
random transitions of
Q
0
:
Proof of correctness of
SZA
.
Lemmas 6 and 7 imply that
Pr[
ρ
(
̂
Q
u
[
X, Y
]
, Q
m
u
0
0
)
≤
8
mε
]
≥
1
−
4
mε.
By Lemma 3, if
x
and
y
are such that
ρ
(
̂
Q
u
[
x, y
]
, Q
m
u
0
0
)
≤
8
mε
, then
̂
Q
u
[
x, y
](
q
;
Z
)
∼
8
mε
Q
m
u
0
0
(
q
;
U
dm
u
0
).
An averaging argument completes the proof.
4.5 Efficiency
The seed length of
SZA
is
ℓ
+
u
∆ +
d
, which is
O
(
s
+
u
log(
w/ε
)). We argue that
SZA
can be
implemented to run in
O
(
s
+
u
log(
w/ε
)) space through mutual recursion involving two subroutine
s.
The first subroutine, given
i, r, z
′
, computes
̂
Q
i
[
x, y
](
r
;
z
′
):
1. If
i
= 0, just consult the input directly. Otherwise:
2. Use the second subroutine to obtain each required entry of
M
(
̂
Pow
(
̂
Q
i
−
1
[
x, y
]
, x
)). Apply the
definition of
̂
Q
i
directly.
The space used by this subroutine is only
O
(log(
w/ε
)) plus the space required for computing each
matrix entry. The second subroutine, given
i, r, v
, computes
M
(
̂
Pow
(
̂
Q
i
[
x, y
]
, x
))
rv
:
1. Initialize
ξ
= 0. For all
z
′
∈ {
0
,
1
}
d
:
(a) Use the oracle to compute
̂
Pow
(
̂
Q
i
[
x, y
]
, x
)(
r
;
z
′
). If it gives
v
, set
ξ
:=
ξ
+ 2
−
d
. When
the oracle makes reads to its automaton/start state inputs,
use the first subroutine to
compute the necessary values of
̂
Q
i
[
x, y
]. When the oracle makes reads to its seed inputs,
(re)compute
Samp
(
x, z
′
) to obtain the appropriate bit.
2. Output
ξ
.
This subroutine’s space usage can get up to
O
(
s
+ log(
w/ε
)) for computing the sampler, but before
each recursive call, it erases all but
O
(log(
w/ε
)) bits. By induction, this shows that the total
space usage of each of these two subroutines (including now t
he space used for recursive calls) is
O
(
s
+ (
i
+ 1) log(
w/ε
)). It follows that the space used by
SZA
is
O
(
s
+
u
log(
w/ε
)), since it just
requires a call to the first subroutine with
i
=
u
.
In this implementation, the maximum number of unresolved or
acle invocations at any time is
indeed
u
, and there is indeed at most one unresolved read of a seed. Thi
s completes the proof of
Theorem 2.
5 Transforming simulators into targeted PRGs
Recall from Section 1.3 that to prove the harder direction of
our main result, we require three
transformations: an assumed transformation of targeted ps
eudorandom generators into simulation
advice generators, the SZA transformation, and a transform
ation of simulators into targeted pseu-
dorandom generators. In this section, we construct the last
transformation.
14
We state our transformation in terms of the Ladner-Lynch (LL
) oracle model [LL76]. This
model is simpler than the implicit oracle model of Section 3.
An LL-model oracle algorithm has a
single write-only oracle tape. When the algorithm makes a qu
ery, the contents of the oracle tape
are erased, and the answer to the query is stored in the algori
thm’s state. Symbols written on
the oracle tape do not count toward the algorithm’s space com
plexity. For a non-Boolean oracle
f
:
{
0
,
1
}
∗
→ {
0
,
1
}
∗
, the oracle algorithm is required to specify an index
i
along with the query
string
x
; the oracle responds with
f
(
x
)
i
. We emphasize that as with the SZA transformation, this
oracle model is only used to cleanly express the transformat
ion; ultimately, we will plug in actual
algorithms in place of the oracle.
Lemma 8.
There exists a deterministic LL-model oracle algorithm
G
such that if
Sim
is an
ε
-
simulator for
Q
m
wm,d
with seed length
s
, then:
1.
G
Sim
is a targeted
(2
mw
2
ε
)
-pseudorandom generator against
Q
m
w,d
.
2.
G
Sim
has seed length
s
and space complexity
O
(
s
+
d
+ log
w
+ log
m
)
.
To prove Lemma 8, we use
Sim
to choose a final state, and then we use
Sim
to “reverse engineer”
a string that brings
Q
to that final state. This reverse engineering process is a str
aightforward
application of the method of conditional probabilities.
Proof.
Given (
Q, q, x
):
1. Let
Q
′
be the (
wm, d
)-automaton formed by adding dummy states to
Q
. Use the oracle to
set
R
:=
Sim
(
Q
′
, q, x
).
2. Initialize
v
=
q
. For
i
= 0 to
m
−
1:
(a) For each
z
∈ {
0
,
1
}
d
, let
v
z
=
Q
(
v
;
z
).
(b) Let
Q
′
be a (
wm, d
)-automaton that simulates
m
−
i
steps of
Q
, with
v
′
z
being the start
state corresponding to
v
z
and
R
′
being the end state corresponding to
R
.
(c) Compute the
z
∈ {
0
,
1
}
d
that maximizes #
{
x
′
:
Sim
(
Q
′
, v
′
z
, x
′
) =
R
′
}
, breaking ties
arbitrarily.
(d) Print
z
and set
v
:=
v
z
.
Clearly,
G
outputs
dm
bits and uses
O
(
s
+
d
+log
w
+log
m
) space. Proof of correctness: For
t, r
∈
[
w
]
and
i
∈ {
0
, . . . , m
−
1
}
, let
p
t,r
[
i
] = Pr[
Q
m
−
i
(
t
;
U
m
−
i
) =
r
]. We show by induction on
i
that at the
beginning of iteration
i
of the loop on line 2,
p
v,R
[
i
]
≥
p
q,R
[0]
−
2
iε
. Base case: At the beginning
of iteration
i
= 0,
v
=
q
. Inductive step: Consider the execution of iteration
i
of the loop. By the
simulator guarantee, there is some
z
∈ {
0
,
1
}
d
such that #
{
x
′
:
Sim
(
Q
′
, v
′
z
, x
′
) =
R
} ≥
(
p
v,R
[
i
]
−
ε
)2
s
.
Therefore,
G
chooses a
z
that also satisfies that inequality. Therefore, applying th
e simulator
guarantee again,
p
v
z
,R
[
i
+ 1]
≥
p
v,R
[
i
]
−
2
ε
. This completes the induction.
Now, let
X
∼
U
s
, and let
Y
=
G
Sim
(
Q, q, X
). Fix an arbitrary state
r
∈
[
w
]; we will show that
Pr[
Q
m
(
q
;
Y
) =
r
] is close to Pr[
Q
m
(
q
;
U
dm
) =
r
]. Say
r
is
typical
if
p
q,r
[0]
≥
2
mε
. For the first case,
suppose
r
is typical. By the fact that we proved by induction, Pr[
Q
m
(
q
;
Y
) =
R
|
R
is typical] = 1.
Therefore,
Pr[
Q
m
(
q
;
Y
) =
r
] = Pr[
Q
m
(
q
;
Y
) =
r
|
R
=
r
]
·
Pr[
R
=
r
] + Pr[
Q
m
(
q
;
Y
) =
r
|
R
6
=
r
]
·
Pr[
R
6
=
r
]
= Pr[
R
=
r
] + Pr[
Q
m
(
q
;
Y
) =
r
|
R
6
=
r
]
·
Pr[
R
6
=
r
]
.
15
This expression is
lower
bounded by Pr[
R
=
r
], which is lower bounded by Pr[
Q
m
(
q
;
U
dm
) =
r
]
−
ε
by the simulator guarantee. On the other hand, the expressio
n is
upper
bounded by Pr[
R
=
r
] + Pr[
R
is atypical], which is upper bounded by Pr[
Q
m
(
q
;
U
dm
) =
r
] +
ε
+ 2
mwε
by the simulator
guarantee, the definition of typicality, and the union bound
.
For the second case, suppose
r
is atypical. Then
Q
m
(
q
;
Y
) =
r
implies that
R
is atypical,
which happens with probability at most 2
mwε
+
ε
by the definition of typicality and the simulator
guarantee.
Therefore, in either case, Pr[
Q
m
(
q
;
Y
) =
r
] is within
±
(2
mw
+ 1)
ε
of Pr[
Q
m
(
q
;
U
dm
) =
r
].
Statistical distance is half
L
1
distance, so the error of
G
Sim
is at most
1
2
w
(2
mw
+1)
ε
≤
2
mw
2
ε
.
6 Proof of Theorem 1
6.1 Composing the transformations
In this section, we compose the transformation of Condition
2 of Theorem 1, the SZA transforma-
tion, and the transformation of Section 5. (In the overview o
f Section 1.3, this corresponds to the
composition of steps 1, 2, and 3.) The composition is a transf
ormation on targeted pseudorandom
generators:
Lemma 9.
Assume Condition
2
of Theorem
1
is true. Fix a constant
β >
0
, sufficiently small
constants
σ > η > γ >
0
, and a constant
μ
∈
(
γ,
1
−
β
]
. Suppose there is a family
{
Gen
w
}
, where
Gen
w
is an efficiently computable targeted
ε
-pseudorandom generator against
Q
m
w,
1
with seed length
s
satisfying
s
≤
O
(log
1+
σ
w
)
,
log(1
/ε
) = log
1+
η
w,
log
m
≥
log
μ
w.
Then there is another family
{
Gen
′
w
}
, where
Gen
′
w
is an efficiently computable targeted
ε
′
-pseudorandom
generator against
Q
m
′
w,
1
with seed length
s
′
satisfying
s
′
≤
O
(log
1+max
{
σ,β
}
+4
η
w
)
,
log(1
/ε
′
)
≥
Ω(log
1+
η
−
γ
w
)
,
log
m
′
≥
log
μ
+
β
w.
All the hard work of proving Lemma 9 has already been done in Se
ctions 4 and 5; conceptually,
the proof is simply by composing. Some technicalities compl
icate matters slightly. First, we need
two little lemmas to deal with the fact that
d >
1 in Theorem 2, to deal with the fact that Theorem 2
is phrased in terms of automata with fail states, and to deal w
ith the relationship between
w
and
m
in Lemma 8.
Lemma 10.
Suppose
Gen
is an
ε
-simulation advice generator for
Q
m
(
w
+1)2
d
,
1
. Then
Gen
is also an
ε
-simulation advice generator for
̃
Q
⌊
m/d
⌋
w,d
.
Proof.
Let
S
be the logspace algorithm such that
S
(
Q, q,
Gen
(
x
)) is an
ε
-simulator for
Q
m
(
w
+1)2
d
,
1
.
Let
a
be the output length of
Gen
. For a (
w, d
)-automaton with fail state
Q
, a start state
q
∈
[
w
+1],
and a string
y
∈ {
0
,
1
}
a
, let
S
′
(
Q, q, y
) behave as follows:
1. Let
Q
′
be the ((
w
+ 1)2
d
,
1)-automaton that simulates
Q
. (One step of
Q
is simulated by
d
steps of
Q
′
; the state space of
Q
′
is [
w
+ 1]
× {
0
,
1
}
<d
.) Let
q
′
be the start state of
Q
′
corresponding to
q
.
16
2. Let
r
′
=
S
(
Q
′
, q
′
, y
).
3. Return the state
r
∈
[
w
+ 1] that corresponds to
r
′
.
The maps (
Q, q, y
)
7→
(
Q
′
, q
′
, y
) and
r
′
7→
r
are computable in logspace, so
S
′
can be implemented
to run in logspace. Clearly,
S
′
(
Q, q,
Gen
(
x
)) is an
ε
-simulator for
̃
Q
⌊
m/d
⌋
w,d
.
Lemma 11.
There exists a deterministic LL-model oracle algorithm
R
with the following properties.
Pick
m
≤
m
′
and
d
≤
d
′
. Suppose
Sim
is an
ε
-simulator for
̃
Q
m
′
wm
(
m
+1)
,d
′
with seed length
s
. Then
R
Sim
m,d
is an
ε
-simulator for
Q
m
wm,d
with seed length
s
. (Here
m, d
are inputs to
R
; we write them as
subscripts merely to separate them from the usual simulator
inputs.) Further,
R
Sim
m,d
only uses space
O
(
d
′
+ log
w
+ log
m
)
.
Proof.
Given (
Q, q, x
) and oracle access to
Sim
:
1. Let
Q
′
be a (
wm
(
m
+ 1)
, d
′
)-automaton with fail state on state space [
wm
]
×
[
m
+ 1] (plus a
fail state) defined by
Q
′
((
q, t
);
y
) =
{
(
Q
(
q
;
y
↾
d
)
, t
+ 1) if
t
≤
m
(
q, t
)
if
t
=
m
+ 1
.
Here
y
↾
d
denotes the first
d
bits of
y
.
2. Output the first coordinate of
Sim
(
Q
′
,
(
q,
1)
, x
).
The first coordinate of (
Q
′
)
m
′
((
q,
1);
U
m
′
d
′
) is distributed identically to
Q
m
(
q
;
U
md
), and applying
a deterministic function (such as “the first coordinate of”)
can only make distributions closer, so
this algorithm is correct. Clearly,
Q
′
can be computed from
Q
in space
O
(
d
′
+ log
w
+ log
m
).
Now we are ready to prove Lemma 9; the proof mainly consists in
verifying parameters.
Proof of Lemma
9
.
Using Condition 2 of Theorem 1, transform the family
{
Gen
w
}
into a family
{
AdvGen
w
}
of simulation advice generators. For each
w
, let
Sim
w
be the simulator induced by
AdvGen
(
w
+1)2
d
using Lemma 10, where
d
=
⌈
c
[log
1+
η
−
γ
(
w
) + log(
w
)]
⌉
and
c
is the constant in
Theorem 2. Define
Sim
′
w
=
SZA
Sim
w
m
′
where log
m
′
=
⌈
log
μ
+
β
w
⌉
.
Define
Sim
′′
w
=
R
Sim
′
wm
′
(
m
′
+1)
m
′
,
1
,
where
R
is the algorithm of Lemma 11. Finally, define
Gen
′
w
=
G
Sim
′′
w
,
where
G
is the algorithm of Lemma 8.
Now that we have constructed
Gen
′
w
, we show that our construction worked. Since log
1+
η
−
γ
w
is
monotone increasing,
Gen
′
(
w
+1)2
d
can be thought of as having error
ε
0
where log(1
/ε
0
) = log
1+
η
−
γ
w
.
Therefore,
Sim
w
is an
ε
0
-simulator for
̃
Q
m
0
w,d
, where log
m
0
≥
Ω(log
μ
−
γ
(
w
)
−
log(
d
)) = Ω(log
μ
−
γ
w
).
Observe that the chosen
d
value is exactly
⌈
c
log(
w/ε
0
)
⌉
. Therefore, by Theorem 2,
Sim
′
w
is
a (12
wε
0
)-simulator for
̃
Q
m
1
w,d
for some
m
1
≥
m
′
. Again using monotonicity, we can think of
17