# Pseudorandom generators for unbounded-width permutation branching programs

### Citation:

Hoza, William M., Edward Pyne, and Salil Vadhan. “Pseudorandom generators for unbounded-width permutation branching programs.” 12th Innovations in Theoretical Computer Science (ITCS '21) . Leibniz International Proceedings in Informatics (LIPIcs), 2021.
 ECCC 2020.pdf 865 KB ITCS 2021.pdf 621 KB

### Abstract:

Version History:

Preliminary version posted on ECCC TR20-138 (PDF version attached as ECCC 2020).

Talks: The ITCS talk for this paper, presented by Edward Pyne, is currently available on YouTube; click the embedded link to view.

We prove that the Impagliazzo-Nisan-Wigderson [Impagliazzo et al., 1994] pseudorandom generator (PRG) fools ordered (read-once) permutation branching programs of unbounded width with a seed length of $$\tilde{O} (\log d + \log n ⋅ \log(1/\epsilon))$$, assuming the program has only one accepting vertex in the final layer. Here, $$n$$ is the length of the program, $$d$$ is the degree (equivalently, the alphabet size), and $$\epsilon$$ is the error of the PRG. In contrast, we show that a randomly chosen generator requires seed length $$\Omega (n \log d)$$ to fool such unbounded-width programs. Thus, this is an unusual case where an explicit construction is "better than random."

Except when the program’s width $$w$$ is very small, this is an improvement over prior work. For example, when $$w = \mathrm{poly} (n)$$ and $$d = 2$$, the best prior PRG for permutation branching programs was simply Nisan’s PRG [Nisan, 1992], which fools general ordered branching programs with seed length $$O (\log (wn/\epsilon) \log n)$$. We prove a seed length lower bound of $$\tilde{\Omega} (\log d + \log n ⋅ \log(1/\epsilon))$$for fooling these unbounded-width programs, showing that our seed length is near-optimal. In fact, when$$\epsilon ≤ 1/\log n$$, our seed length is within a constant factor of optimal. Our analysis of the INW generator uses the connection between the PRG and the derandomized square of Rozenman and Vadhan [Rozenman and Vadhan, 2005] and the recent analysis of the latter in terms of unit-circle approximation by Ahmadinejad et al. [Ahmadinejad et al., 2020].

Publisher's Version

Last updated on 07/07/2021