Implications of Better PRGs for Permutation Branching Programs

We study the challenge of derandomizing constant-width standard-order read-once branching programs (ROBPs). Let $c \in [1, 2)$ be any constant. We prove that if there are explicit pseudorandom generators (PRGs) for width-$6$ length-$n$ permutation ROBPs with error $1/n$ and seed length $\widetilde{O}(\log^c n)$, then there are explicit hitting set generators (HSGs) for width-$4$ length-$n$ ROBPs with threshold $1/\mathrm{polylog}(n)$ and seed length $\widetilde{O}(\log^c n)$.

For context, there are known explicit PRGs that fool constant-width permutation ROBPs with error $\varepsilon$ and seed length $O(\log n \cdot \log(1/\varepsilon))$ (Koucký, Nimbhorkar, and Pudlák STOC 2011; De CCC 2011; Steinke ECCC 2012). When $\varepsilon = 1/n$, there are known constructions of weighted pseudorandom generators (WPRGs) that fool polynomial-width permutation ROBPs with seed length $\widetilde{O}(\log^{3/2} n)$ (Pyne and Vadhan CCC 2021; Chen, Hoza, Lyu, Tal, and Wu FOCS 2023; Chattopadhyay and Liao ITCS 2024), but unweighted PRGs with seed length $o(\log^2 n)$ remain elusive. Meanwhile, for width-$4$ ROBPs, there are no known explicit PRGs, WPRGs, or HSGs with seed length $o(\log^2 n)$.

Our reduction can be divided into two parts. First, we show that explicit low-error PRGs for width-$6$ permutation ROBPs with seed length $\widetilde{O}(\log^c n)$ would imply explicit low-error PRGs for width-$3$ ROBPs with seed length $\widetilde{O}(\log^c n)$. This would improve Meka, Reingold, and Tal's PRG (STOC 2019), which has seed length $o(\log^2 n)$ only when the error parameter is relatively large. Second, we show that for any $w$, $n$, $s$, and $\varepsilon$, an explicit PRG for width-$w$ ROBPs with error $0.01/n$ and seed length $s$ would imply an explicit $\varepsilon$-HSG for width-$(w + 1)$ ROBPs with seed length $O(s + \log n \cdot \log(1/\varepsilon))$.

This is a paper about pseudorandom generators. In general, a "pseudorandom generator" is an algorithm that makes a few coin tosses and outputs a long sequence of bits $x_1, x_2, x_3, \dots$ that "appear random" in some sense. In the context of this paper, the goal is that the output bits should appear random to any observer who has very little memory and who observes the bits one at a time (first $x_1$, then $x_2$, etc.) The observer can also use a "clock," i.e., the observer always knows how many bits they have seen so far.

Our main theorem is a conditional theorem, i.e., we establish a new connection between two interesting unsolved problems, but unfortunately, we don't solve either of them. Suppose that someone (you?) figures out how to design a pseudorandom generator that works well provided that the observer only uses three bits of memory and the observer satisfies a severe "reversibility" condition. Under this assumption, we show how to design something called a "hitting set generator" (a variant of the pseudorandom generator concept) that works well even if the observer does not satisfy the "reversibility" condition, provided that the observer only uses two bits of memory.