Revision #1 Authors: Andrej Bogdanov, William Hoza, Gautam Prakriya, Edward Pyne

Accepted on: 3rd November 2021 18:43

Downloads: 69

Keywords:

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