The Warranty On Nisan’s Generator
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 and are the uniform distributions on and , respectively. The 1-norm is the sum over all states of the absolute value of the difference between and , where means that the FSM goes from its start state to state reading .
Let be computable in polynomial time in and let . Say that is a pseudo-random generator against Finite State Machine FSMs (PRG) for space with parameter if for any FSM with states
See their paper for all the details.
Nisan’s theorem is:
Theorem: There exists such that for any , there exists a function computable in time polynomial in which is a pseudo-random generator against FSMs for space , with parameter .
The definition allows that the machine can only read the “random” bits 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.
Read It Again?
Consider the case of where the FSM is limited to logspace, then the seed is 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 be a PRG against FSMs for space with parameter . Then, the two-pass version is a PRG generator for space and parameter .
Note, the space decreased by a factor of and the error parameter went up by a factor of . What I find beautiful is that this lemma allows them to prove by simply iterating it not too many times——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.
They point out, without any proof, that if there was a PRG that does polynomially many passes and fools logspace machines then . 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 passes for any constant will prove . Actually, I think even more is possible. More in the future on the details of this claim.