We construct improved hitting set generators (HSGs) for ordered (read-once) regular branching programs in two parameter regimes. First, we construct an explicit $\varepsilon$-HSG for unbounded-width regular branching programs with a single accept state with seed length
$$\tilde{O}(\log n \cdot \log(1/\varepsilon)),$$
where $n$ is the length of the program. Second, we construct an explicit $\varepsilon$-HSG for width-$w$ length-$n$ regular branching programs with seed length
$$\tilde{O}\left(\log n \cdot \left(\sqrt{\log(1/\varepsilon)} + \log w \right) + \log(1/\varepsilon)\right).$$
For context, the ``baseline'' in this area is the pseudorandom generator (PRG) by Nisan (Combinatorica 1992), which fools ordered (possibly non-regular) branching programs with seed length $O(\log(wn/\varepsilon) \cdot \log n)$. For regular programs, the state-of-the-art PRG, by Braverman, Rao, Raz, and Yehudayoff (FOCS 2010, SICOMP 2014), has seed length $\tilde{O}(\log(w/\varepsilon) \cdot \log n)$, which beats Nisan's seed length when $\log(w/\varepsilon) = o(\log n)$.
Taken together, our two new constructions beat Nisan's seed length in all parameter regimes except when $\log w$ and $\log(1/\varepsilon)$ are both $\Omega(\log n)$ (for the construction of HSGs for regular branching programs with a single accept vertex).

Extending work by Reingold, Trevisan, and Vadhan (STOC 2006), we furthermore show that an explicit HSG for regular branching programs with a single accept vertex with seed length $o(\log^2 n)$ in the regime $\log w = \Theta(\log(1/\varepsilon)) = \Theta(\log n)$ would imply improved HSGs for genera; ordered branching programs, which would be a major breakthrough in derandomization. Pyne and Vadhan (CCC 2021) recently obtained such parameters for the special case of permutation branching programs.

Minor edits

We construct improved hitting set generators (HSGs) for ordered (read-once) regular branching programs in two parameter regimes. First, we construct an explicit $\varepsilon$-HSG for unbounded-width regular branching programs with a single accept state with seed length
$$\tilde{O}(\log n \cdot \log(1/\varepsilon)),$$
where $n$ is the length of the program. Second, we construct an explicit $\varepsilon$-HSG for width-$w$ length-$n$ regular branching programs with seed length
$$\tilde{O}\left(\log n \cdot \left(\sqrt{\log(1/\varepsilon)} + \log w \right) + \log(1/\varepsilon)\right).$$
For context, the ``baseline'' in this area is the pseudorandom generator (PRG) by Nisan (Combinatorica 1992), which fools ordered (possibly non-regular) branching programs with seed length $O(\log(wn/\varepsilon) \cdot \log n)$. For regular programs, the state-of-the-art PRG, by Braverman, Rao, Raz, and Yehudayoff (FOCS 2010, SICOMP 2014), has seed length $\tilde{O}(\log(w/\varepsilon) \cdot \log n)$, which beats Nisan's seed length when $\log(w/\varepsilon) = o(\log n)$.
Taken together, our two new constructions beat Nisan's seed length in all parameter regimes except when $\log w$ and $\log(1/\varepsilon)$ are both $\Omega(\log n)$ (for the construction of HSGs for regular branching programs with a single accept vertex).

Extending work by Reingold, Trevisan, and Vadhan (STOC 2006), we furthermore show that an explicit HSG for regular branching programs with a single accept vertex with seed length $o(\log^2 n)$ in the regime $\log w = \Theta(\log(1/\varepsilon)) = \Theta(\log n)$ would imply improved HSGs for general ordered branching programs, which would be a major breakthrough in derandomization. Pyne and Vadhan (CCC 2021) recently obtained such parameters for the special case of permutation branching programs.

New results

We construct an explicit $\varepsilon$-hitting set generator (HSG) for regular ordered branching programs of length $n$ and $\textit{unbounded width}$ with a single accept state that has seed length
\[O(\log(n)(\log\log(n)+\log(1/\varepsilon))).\]
Previously, the best known seed length for regular branching programs of width $w$ with a single accept state was by Braverman, Rao, Raz and Yehudayoff (FOCS 2010, SICOMP 2014) and Hoza Pyne and Vadhan (ITCS 2021), which gave
\[O(\log(n)(\log\log(n)+\min\{\log(w),\log(n)\}+\log(1/\varepsilon))).\]
We also give a simple co-HSG for the model with optimal seed length $O(\log n)$.

For the more restricted model of $\textit{permutation}$ branching programs, Hoza Pyne and Vadhan (ITCS 2021) constructed a PRG with seed length matching our HSG, and then Pyne and Vadhan (CCC 2021) developed an error-reduction procedure that gave an HSG (in fact a ``weighted PRG'') with seed length $\widetilde{O}(\log(n)\sqrt{\log(n/\varepsilon)}+\log(1/\varepsilon)).$ We show that if an analogous error-reduction result could be obtained for our HSG, there is an explicit HSG for general ordered branching programs of width $w=n$ with seed length $\widetilde{O}(\log^{3/2}n)$, improving on the $O(\log^2n)$ seed length of Nisan (Combinatorica 1992).