A polynomial-time construction of a hitting set for read-once branching programs of width 3

Recently, an interest in constructing pseudorandom or hitting set generatorsfor restricted branching programs has increased, which is motivated by thefundamental issue of derandomizing space-bounded computations. Suchconstructions have been known only in the case of width 2 and in veryrestricted cases of bounded width. In this paper, we characterize the hittingsets for read-once branching programs of width 3 by a so-called richnesscondition. Namely, we show that such sets hit the class of read-onceconjunctions of DNF and CNF (i.e. the weak richness). Moreover, we prove thatany rich set extended with all strings within Hamming distance of 3 is ahitting set for read-once branching programs of width 3. Then, we show that anyalmost $O(\log n)$-wise independent set satisfies the richness condition. Byusing such a set due to Alon et al. (1992) our result provides an explicitpolynomial-time construction of a hitting set for read-once branching programsof width 3 with acceptance probability $\varepsilon>5/6$. We announced thisresult at conferences more than ten years ago, including only proof sketches,which motivated a number of subsequent results on pseudorandom generators forrestricted read-once branching programs. This paper contains our originaldetailed proof that has not been published yet.Comment: 48 pages, 10 figure