Nisan’s generator can re-read the pseudo-random bits multiple times

Matei David, Periklis Papakonstantinou, and Anastasios Sidiropoulos are three young complexity theorists who are linked by three things, at least. I understand they all were part of the Toronto theory group at the same time, either as students or post docs; they all are interested in various aspects of complexity theory, especially randomness; and they wrote a wonderful paper together.

Today I want to talk about an extension of the famous Nisan pseudo-random number generator that can fool space limited computations. This extension is their joint paper (DPS)— I think the result is quite pretty and has potentially many consequences.

Nisan’s generator comes with an expressed warranty. It starts with the usual:

FOR USERS, WHO ARE COVERED BY PROTECTION LAWS OR REGULATIONS IN THEIR COUNTRY OR, IF DIFFERENT, THEIR COUNTRY OF RESIDENCE, THE BENEFITS CONFERRED BY THIS WARRANTY ARE IN ADDITION TO ALL RIGHTS AND REMEDIES CONVEYED BY SUCH PROTECTION LAWS AND REGULATIONS.

But the critical part for us is this:

The users of this random number generator assume all liability. It is only to be used against space restricted machines, any other use is prohibited. Users must select a really random number for the seed—any attempt to use other than real random bits for the seed are a violation of the operating conditions of the generator. Further, each generated bit is to be read once, not twice, nor three times. Any deviation from this is a violation of the operating conditions and is prohibited.

Note, I converted above text into lowercase. It is well known that all-caps is hard to read—IS THAT WHY WARRANTIES USE ALL CAPS? The DPS paper violates the warranty—or you can say, it enables a less-restrictive one to be written. Let’s see what happens.”

The Nisan Generator

I will first explain the Noam Nisan’s generator in the way they use it in their paper. Here ${U_n}$ and ${U_m}$ are the uniform distributions on ${x \in \{0,1\}^n}$ and ${s \in \{0,1\}^m}$, respectively. The 1-norm is the sum over all states ${q \in Q}$ of the absolute value of the difference between ${\Pr_x(Q(x) = q)}$ and ${\Pr_s(Q(G(s)) = q}$, where ${Q(x) = q}$ means that the FSM goes from its start state ${1}$ to state ${q}$ reading ${x}$.

Let ${G: \{0,1\}^m \rightarrow \{0,1\}^n}$ be computable in polynomial time in ${n}$ and let ${\epsilon,w>0}$. Say that ${G}$ is a pseudo-random generator against Finite State Machine FSMs (PRG) for space ${w}$ with parameter ${\epsilon}$ if for any FSM ${Q}$ with ${2^w}$ states

$\displaystyle ||Q(U_n)-Q(G(U_m))||_1 \le \epsilon.$

See their paper for all the details.

Nisan’s theorem is:

Theorem: There exists ${c>0}$ such that for any ${N>0}$, there exists a function ${G:\{0,1\}^{N^2} \rightarrow \{0,1\}^{N2^{cN}}}$ computable in time polynomial in ${2^{cN}}$ which is a pseudo-random generator against FSMs for space ${cN}$, with parameter ${2^{-cN}}$.

The definition allows that the machine ${Q}$ can only read the “random” bits ${G(U_m)}$ once. They suggest that you think of the bits as placed on a special random tape that is one-way. The machine reads a bit, uses it any way it wishes, and then can move on to the next bit of the tape. The only way it can “recall” the exact bit is by storing it in its limited storage.

Consider the case of where the FSM is limited to logspace, then the seed is ${O(\log^2 n)}$ in size, and the generator creates a polynomial number of pseudo-random bits. In this case they ask: can Nisan’s generator be “misused” and still work? The somewhat surprising answer is yes. They show that it is possible to allow the FSM to treat the random tape as a read-twice tape: that is the machine can read the random bits, and then read them once again. The cost of this is a relatively small change in the parameters of Nisan’s theorem.

This is done without any change to the generator, at all. It really is simply extending the generator’s warranty. The formal lemma that shows this works is:

Lemma: Let ${G:\{0,1\}^m \rightarrow \{0,1\}^n}$ be a PRG against FSMs for space ${2s}$ with parameter ${\epsilon}$. Then, the two-pass version is a PRG generator for space ${s}$ and parameter ${\epsilon \cdot 2^{2s}}$.

Note, the space decreased by a factor of ${2}$ and the error parameter went up by a factor of ${2^{2s}}$. What I find beautiful is that this lemma allows them to prove by simply iterating it not too many times—${O(\log \log n)}$—that we get a PRG which fools a logspace machine, and allows multiple passes over the random tape. Again see their paper for all the bounds.

A very cool result.

Open Problems

They point out, without any proof, that if there was a PRG that does polynomially many passes and fools logspace machines then ${\mathsf{L} \neq \mathsf{NP}}$. They do show that such a generator cannot be the Nisan one—it does break if you try to allow that many passes.

I believe I get how they prove this claim, which is an “aside” in the final part of their paper. I actually conjecture that a much stronger conjecture should be true. Staying with Nisan’s generator, as an example, I believe that allowing ${\log^k n}$ passes for any constant ${k}$ will prove ${\mathsf{L} \neq \mathsf{NP}}$. Actually, I think even more is possible. More in the future on the details of this claim.