Dependencies

Every \(\operatorname {RSPACE}(S)\) computation using \(R\) random bits can be simulated deterministically by enumerating all seeds of the Nisan generator, using \(O(S\log R)\) space and the same simulation rule for every such randomized algorithm.

Let a one-sided-error randomized algorithm use \(R\) random bits and succeed on yes-instances with probability at least \(1/2\). For every \(k\le R\), one can run \(k\) amplified trials using \(O(R\log k)\) random bits and reduce the probability that all trials fail to \((1+o(1))2^{-k}\). More generally, if the success probability is at least \(1/\operatorname {poly}(k)\), polynomially many trials reduce failure to \(2^{-k}\) while still using \(O(R\log k)\) random bits.

Any randomized algorithm running in space \(S\) and using \(R\) random bits can be simulated by an algorithm using only \(O(S\log R)\) random bits and \(O(S\log R)\) space.

Fix integers \(w,n,k \ge 0\). A randomized program that receives its random bits in \(k\) blocks of \(n\) bits and uses at most \(w\) bits of information between two consecutive blocks is represented by a finite state machine \(Q\) with \(2^w\) states over the alphabet \(\{ 0,1\} ^n\). There is a fixed start state and an arbitrary set of accepting states. For every state \(v\) and every block \(a \in \{ 0,1\} ^n\), exactly one outgoing edge from \(v\) is labelled by a set containing \(a\); following that edge is the transition caused by feeding block \(a\) to the original program.

A map \(G:\{ 0,1\} ^m \to (\{ 0,1\} ^n)^k\) is a pseudorandom generator for \(\operatorname {Space}(w)\) and block size \(n\) with parameter \(\varepsilon \) if for every finite state machine \(Q\) of size \(2^w\) over alphabet \(\{ 0,1\} ^n\),

For a finite state machine \(Q\), a sequence \((h_1,\ldots ,h_k)\) is \((\varepsilon ,Q)\)-good if

where \(G_k(*,h_1,\ldots ,h_k)\) is the distribution induced by a uniform \(x \leftarrow \{ 0,1\} ^n\).

Let \(A \subseteq \{ 0,1\} ^n\), \(B \subseteq \{ 0,1\} ^m\), \(h:\{ 0,1\} ^n \to \{ 0,1\} ^m\), and \(\varepsilon {\gt}0\). Write \(\mu (A)=|A|/2^n\) and \(\mu (B)=|B|/2^m\). The function \(h\) is \((\varepsilon ,A,B)\)-independent if

For a vector \(x \in \mathbb R^s\), set \(\left\| x\right\| _1=\sum _i |x_i|\). For an \(s \times s\) matrix \(M\), set

All matrix norms in this blueprint use this induced one-norm.

A map \(G:\{ 0,1\} ^m\to (\{ 0,1\} ^n)^k\) is a pseudo-independent block generator with parameter \(\varepsilon \) if for every sequence of sets \(A_1,\ldots ,A_k\subseteq \{ 0,1\} ^n\),

where \((y_1,\ldots ,y_k)=G(x)\) for uniform \(x\) and \(p_i=|A_i|/2^n\).

Let \(Q\) be a finite state machine with \(s\) states over alphabet \(\{ 0,1\} ^n\) and let \(D\) be a distribution on \((\{ 0,1\} ^n)^k\). The matrix \(Q(D)\) is the \(s \times s\) matrix whose \((i,j)\) entry is the probability that \(Q\), started at state \(i\), reaches state \(j\) after reading a random sequence drawn from \(D\). Let \(U_n\) denote the uniform distribution on \(\{ 0,1\} ^n\).

A map \(G:\{ 0,1\} ^m\to \{ 0,1\} ^R\) is a pseudorandom generator for \(\operatorname {Space}(S)\) with parameter \(\varepsilon \) if for every randomized \(\operatorname {Space}(S)\) algorithm \(A\) and every fixed input to \(A\),

Let \(\mathcal{H}\) be a finite set of functions \(h:\{ 0,1\} ^n \to \{ 0,1\} ^m\). The family \(\mathcal{H}\) is universal if for all distinct \(x_1,x_2 \in \{ 0,1\} ^n\) and all \(y_1,y_2 \in \{ 0,1\} ^m\),

Thus a uniformly selected member of \(\mathcal{H}\) sends two distinct inputs to two prescribed outputs with exactly the probability obtained from two independent uniform \(m\)-bit strings.

For \(d\)-regular graphs on \(n\) vertices, a sequence over \(\{ 1,\ldots ,d\} \) is universal if, for every connected \(d\)-regular graph with a fixed ordering of the incident edges at each vertex and every starting vertex, following the edge indices in the sequence visits every vertex.

If \((h_1,\ldots ,h_k)\) is \((\eta ,Q)\)-good, then the difference between the acceptance probability of \(Q\) on a uniform string in \((\{ 0,1\} ^n)^{2^k}\) and on \(G_k(x,h_1,\ldots ,h_k)\) with uniform \(x\) is at most \(\eta \).

Suppose Lemma 21 has been proved for \(k-1\). Then for random \(h_1,\ldots ,h_{k-1}\leftarrow \mathcal{H}\), the probability that \((h_1,\ldots ,h_{k-1})\) is not \(((2^{k-1}-1)\varepsilon ,Q)\)-good is at most \(2^{6w}(k-1)/(\varepsilon ^2 2^{2n})\).

Fix \(h_1,\ldots ,h_{k-1}\). For states \(i,\ell ,j\) of a \(2^w\)-state machine \(Q\), let \(B_{i,\ell }^{h_1,\ldots ,h_{k-1}}\) be the set of seeds \(x\) for which \(G_{k-1}(x,h_1,\ldots ,h_{k-1})\) takes \(Q\) from \(i\) to \(\ell \). With probability at least \(1-2^{6w}/(\varepsilon ^2 2^{2n})\) over \(h_k\leftarrow \mathcal{H}\), the function \(h_k\) is \((2^{-2w}\varepsilon ,B_{i,\ell },B_{\ell ,j})\)-independent for every triple \(i,\ell ,j\).

The convolution family of Construction 4 is a universal family of functions from \(\{ 0,1\} ^n\) to \(\{ 0,1\} ^m\).

There is a constant \(c{\gt}0\) such that for all integers \(n\) and \(k\le cn\), the recursive generator \(G_k:\{ 0,1\} ^n\times \mathcal{H}^k\to (\{ 0,1\} ^n)^{2^k}\) is a pseudorandom generator for \(\operatorname {Space}(cn)\) and block size \(n\) with parameter \(2^{-cn}\).

For \(k=0\), the empty hash sequence is \((0,Q)\)-good for every finite state machine \(Q\).

Let \(\mathcal{H}\) be a universal family of functions \(\{ 0,1\} ^n\to \{ 0,1\} ^n\), let \(Q\) be a finite state machine of size \(2^w\), and let \(k\ge 0\). Then

With the notation of Lemma 8, for every \(\delta {\gt}0\),

Let \(\mathcal{H}\) be universal, \(A \subseteq \{ 0,1\} ^n\), and \(B \subseteq \{ 0,1\} ^m\). For \(M(x,h)=1\) if \(h(x)\in B\) and \(M(x,h)=0\) otherwise, define \(f(h)=\mathbb {E}_{x \leftarrow A}M(x,h)\) and \(p=\mu (B)\). Then \(\mathbb {E}_{h \leftarrow \mathcal{H}}f(h)=p\), and \(h\) is \((\varepsilon ,A,B)\)-independent exactly when \(\left|p-f(h)\right|\le \varepsilon /\mu (A)\).

With the notation of Lemma 7,

If the simultaneous independence event of Lemma 18 holds, then

If \((h_1,\ldots ,h_{k-1})\) is \(((2^{k-1}-1)\varepsilon ,Q)\)-good, then

For compatible real matrices \(M,N\): \(\left\| M+N\right\| _1\le \left\| M\right\| _1+\left\| N\right\| _1\), \(\left\| MN\right\| _1\le \left\| M\right\| _1\left\| N\right\| _1\), \(\left\| M\right\| _1=\max _i\sum _j |M_{ij}|\) in the row-vector convention of the paper, if every entry of an \(s \times s\) matrix has absolute value at most \(\eta \) then \(\left\| M\right\| _1\le s\eta \), and every transition probability matrix has norm \(1\).

Let \(G\) be a pseudorandom generator that fools logarithmic-space machines with sufficiently small constant error and outputs strings encoding walks of length \(L\) in \(d\)-regular \(n\)-vertex graphs. Then concatenating all possible outputs of \(G\) gives a universal traversal sequence whose length is \(L\cdot 2^{\text{seed length}}\).

For \(N=2^n\), the expected number of candidate choices made by Algorithm 38 before a prime is found is \(O(n)\).

There is a randomized primality-test stage using \(O(n)\) random bits and \(O(n)\) retained space such that every prime is accepted and every composite \(n\)-bit integer is rejected with probability at least \(1/2\) by one stage. Repeating \(O(n)\) independent stages makes the probability of accepting a composite exponentially small in \(n\).

Let \(A \subseteq \{ 0,1\} ^n\), \(B \subseteq \{ 0,1\} ^m\), let \(\mathcal{H}\) be a universal family of functions \(\{ 0,1\} ^n \to \{ 0,1\} ^m\), and let \(\varepsilon {\gt}0\). Then

If \(G:\{ 0,1\} ^m\to (\{ 0,1\} ^n)^k\) is a pseudorandom generator for \(\operatorname {Space}(\log (k+2))\) and block size \(n\) with parameter \(\varepsilon \), then \(G\) is a pseudo-independent block generator with parameter \(\varepsilon \).

If \(G:\{ 0,1\} ^m\to (\{ 0,1\} ^n)^k\) is a pseudorandom generator for \(\operatorname {Space}(S)\) and block size \(n\) with parameter \(\varepsilon \), then the concatenated output of \(G\) is a pseudorandom generator for ordinary \(\operatorname {Space}(S)\) algorithms with the same parameter \(\varepsilon \).

Suppose a randomized computation is divided into stages, each stage consumes at most \(n\) random bits, and the information retained between stages uses at most \(w\) bits. Then replacing the stage randomness by the blocks of a pseudorandom generator for \(\operatorname {Space}(w)\) and block size \(n\) changes the final output distribution by at most the generator parameter, for every event that can be tested from the final state.

The pseudo-independent block generator also amplifies BPP-type algorithms: if each trial is correct with probability at least \(2/3\), then using \(O(R\log k)\) random bits for \(k\) generated trials and taking the majority reduces the error exponentially in \(k\), up to the generator error.

There is a constant \(c{\gt}0\) such that for all integers \(R\) and \(k\le 2^R\), there is an explicit pseudo-independent block generator with parameter \(2^{-R}\) that converts \(cR\log k\) random bits into \(k\) strings of length \(R\).

A nearly uniform random prime in the range \(\{ 1,\ldots ,2^n\} \) can be generated using only \(O(n\log n)\) truly random bits.

For all \(R\) and \(S\), there is an explicit pseudorandom generator

for \(\operatorname {Space}(S)\) with parameter \(2^{-S}\). The generator can be computed in time polynomial in \(R\) and \(S\) and in space \(O(S\log R)\).

For all \(n\) and \(2\le d{\lt}n\), there are explicit universal traversal sequences of length \(n^{O(\log n)}\) for \(d\)-regular \(n\)-vertex graphs. Moreover, the sequences can be produced by a deterministic Turing machine using space logarithmic in the sequence length.