ECCC-Report TR21-143https://eccc.weizmann.ac.il/report/2021/143Comments and Revisions published for TR21-143en-usFri, 03 Jun 2022 16:16:01 +0300
Revision 2
| Hitting Sets For Regular Branching Programs |
Andrej Bogdanov,
William Hoza,
Gautam Prakriya,
Edward Pyne
https://eccc.weizmann.ac.il/report/2021/143#revision2We 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.Fri, 03 Jun 2022 16:16:01 +0300https://eccc.weizmann.ac.il/report/2021/143#revision2
Revision 1
| Hitting Sets for Regular Branching Programs |
Andrej Bogdanov,
William Hoza,
Gautam Prakriya,
Edward Pyne
https://eccc.weizmann.ac.il/report/2021/143#revision1We 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.Wed, 03 Nov 2021 18:43:33 +0200https://eccc.weizmann.ac.il/report/2021/143#revision1
Paper TR21-143
| Hitting Sets For Regular Branching Programs |
Edward Pyne
https://eccc.weizmann.ac.il/report/2021/143We 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).Wed, 13 Oct 2021 18:27:42 +0300https://eccc.weizmann.ac.il/report/2021/143