TR24-137 Authors: Dean Doron, William Hoza

Publication: 10th September 2024 00:05

Downloads: 143

Keywords:

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))$.