Simplyfing Armoni's PRG

Oded's comments

(I had this paper on my reading list for over a month, but only got to it now.)

The space-fooling pseudorandom generators (PRGs) of Noam Nisan (N90) and Nisan and Zuckerman (NZ93) are among my most favorite constructions and results (see Sec 8.4.2 in my book on complexity theory).

While I tend to think of these constructions as fundamentally different, the current paper highlights common themes, which were already visible in the works of INW94 and Armoni (and became more visible in subsequent works). This becomes most apartent in a single construction that interpolates the results of N90 and NZ93, by presenting a generalization (or rather a flexible version) of basic INW94 step (of recylcing randomness once) and using it in a highly transparent manner.

Indeed, the basic step in all the aforementioned construction is a recycling of randomness.

• In N90, the recycling is performed by a hashing function, which has description length linear in the strings on which it operate but the (``mixing'') effect of the recycling is analyzed with respect to an exponential number of ROBP derived from the original ROBP.
  (The full construction uses a balanced binary tree in which the basic steps correspond to internal nodes.)
• In NZ93, the recycling is performed by a randomness extractor, which is applied several times on the same string.
  (The full construction uses a constant-height balanced tree of almost-linear arity in which the basic steps correspond to internal nodes.)
• In INW94, recycling is also performed (essentially) by an extractor, but the applications are iterative as in N90 rather than as in NZ93.
  (As in N90, the full construction uses a balanced binary tree in which the basic steps correspond to internal nodes.)
• Here, the authors take advantage on the (evident) asymmetry between the original string and the resulting string, an asymmetry which is dramatic in the parameter regime of NZ93 but not in the one of N90.
  (In contrast to all the foregoing, the full construction uses an unbalanced binary tree in which the basic steps correspond to internal nodes; the leaves in the positional tree are on paths that have the same number of `right' moves.)

Original abstract

We propose a simple variant of the INW pseudo-random generator, where blocks have varying lengths, and prove it gives the same parameters as the more complicated construction of Armoni's PRG. This shows there is no need for the specialized PRGs of Nisan and Zuckerman and Armoni, and they can be obtained as simple variants of INW.

For the construction to work we need space-efficient extractors with tiny entropy loss. We use the extractors from Chattopadhyay et. al instead of Guruswami et. al taking advantage of the very high min-entropy regime we work with.

We remark that using these extractors has the additional benefit of making the dependence on the branching program alphabet $\Sigma$ correct.

See ECCC TR25-065.