A sufficient condition for sets hitting the class of read-once branching programs of width 3

We characterize the hitting sets for read-once branching programs of width 3 by a so-called richness condition which is independent of a rather technical definition of branching programs. The richness property proves to be (in certain sense) necessary and sufficient condition for such hitting sets. In particular, we show that any rich set extended with all strings within Hamming distance of 3 is a hitting set for width-3 read-once branching programs. Applying this result to an example of an efficiently constructible rich set from our previous work we achieve an explicit polynomial time construction of an e -hitting set for read-once branching programs of width 3 with acceptance probability e >11/12.