\(\renewcommand{\epsilon}{\varepsilon}\) \(\renewcommand{\hat}{\widehat}\) \(\DeclareMathOperator*{\E}{\mathbb{E}}\)

Back to list of papers

Hitting Sets for Regular Branching Programs

By Andrej Bogdanov, William M. Hoza, Gautam Prakriya, and Edward Pyne

Read the paper: ECCCCCC proceedings

Abstract (for specialists)

We construct improved hitting set generators (HSGs) for ordered (read-once) regular branching programs in two parameter regimes. First, we construct an explicit \(\epsilon\)-HSG for unbounded-width regular branching programs with a single accept state with seed length \[ \widetilde{O}(\log n \cdot \log(1/\epsilon)), \] where \(n\) is the length of the program. Second, we construct an explicit \(\epsilon\)-HSG for width-\(w\) length-\(n\) regular branching programs with seed length \[ \widetilde{O}\left(\log n \cdot \left(\sqrt{\log(1/\epsilon)} + \log w \right) + \log(1/\epsilon)\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/\epsilon) \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 \(\widetilde{O}(\log(w/\epsilon) \cdot \log n)\), which beats Nisan's seed length when \(\log(w/\epsilon) = 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/\epsilon)\) 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/\epsilon)) = \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.

Not-so-abstract (for curious outsiders)

⚠️ This summary might gloss over some important details.

A "hitting set" is a set of binary strings \(H\) with a guarantee along the following lines: Let \(P\) be any property of binary strings such that (a) many strings have property \(P\) and (b) it's easy to check whether a given string has property \(P\). Then there is at least one string in \(H\) with property \(P\). (What exactly does "easy" mean? That varies depending on context. The meaning of "easy" in the context of our paper is somewhat technical, but it's related to computing with low memory.) In the paper, we present a couple of hitting sets that are smaller than all previously discovered hitting sets in some cases.

Ted posted a manuscript online (authored solely by himself) in October 2021; we posted an updated version online (with the current author list) in November 2021; I presented the paper at CCC in July 2022. Some of the material in the ECCC version is omitted from the CCC proceedings version.

Expository material:

[Video] My prerecorded presentation for CCC (July 2022). Here are the slides from that presentation. I used very similar slides for my live, in-person CCC presentation.

Ted discusses the paper in this remote presentation for the ETH Zurich Algorithms and Complexity Seminar (December 2021).