Prof. Dean Doron

We study the challenge of derandomizing constant-width standard-order read-once branching programs (ROBPs). Let c ∈ [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 O^e(log^c n), then there are explicit hitting set generators (HSGs) for width-4 length-n ROBPs with threshold 1/polylog(n) and seed length O^e(log^c n). For context, there are known explicit PRGs that fool constant-width permutation ROBPs with error ϵ and seed length O(log n · log(1/ϵ)) (Koucký, Nimbhorkar, and Pudlák STOC 2011; De CCC 2011; Steinke ECCC 2012). When ϵ = 1/n, there are known constructions of weighted pseudorandom generators (WPRGs) that fool polynomial-width permutation ROBPs with seed length O^e(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² n) remain elusive. Meanwhile, for width-4 ROBPs, there are no known explicit PRGs, WPRGs, or HSGs with seed length o(log² 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 O^e(log^c n) would imply explicit low-error PRGs for width-3 ROBPs with seed length O^e(log^c n). This would improve Meka, Reingold, and Tal's PRG (STOC 2019), which has seed length o(log² n) only when the error parameter is relatively large. Second, we show that for any w, n, s, and ϵ, an explicit PRG for width-w ROBPs with error 0.01/n and seed length s would imply an explicit ϵ-HSG for width-(w + 1) ROBPs with seed length O(s + log n · log(1/ϵ)).