The relationship between deterministic and probabilistic computations is one of the central issues in complexity theory. This problem can be tackled by constructing polynomial time hitting set generators which, however, belongs to the hardest problems in computer science even for severely restricted computational models. We consider read-once branching (1-branching) programs of polynomial size for which such constructions have been known only in the case of width 2 and in very restricted cases of bounded width (e.g. permutation or regular oblivious read-once branching programs). In this paper, we characterize the hitting sets for read-once branching programs of width 3 by a necessary so-called richness condition, which is independent of a rather technical formalism of branching programs. This condition proves to be sufficient in a sense that any rich set extended with all strings within Hamming distance of 3 is a hitting set for width-3 1-branching programs that are weakly oblivious (i.e. at each level where only one node branches to its two different successors, all nodes are labeled with the same variable). Then, we prove that any almost $O(\log n)$-wise independent set satisfies the richness condition. By using such a set due to Alon et al. (1992) our result provides an explicit polynomial time construction of a hitting set for (weakly oblivious) read-once branching programs of width 3 with acceptance probability $\varepsilon>\sqrt{12/13}$.
Yet another revision focuses solely on the second part of the report concerning the proof that, for suitable $k$, almost $k$-wise independent sets satisfy the richness condition. We have structured the proof by splitting it into several lemmas and corrected the argument for the cardinalities of partition classes with a constant number of occurrences (less frequent cardinalities).
The relationship between deterministic and probabilistic computations is one of the central issues in complexity theory. This problem can be tackled by constructing polynomial time hitting set generators which, however, belongs to the hardest problems in computer science even for severely restricted computational models. We consider read-once branching (1-branching) programs of polynomial size for which such constructions have been known only in the case of width 2 and in very restricted cases of bounded width (e.g. permutation or regular oblivious read-once branching programs). In this paper, we characterize the hitting sets for read-once branching programs of width 3 by a necessary so-called richness condition, which is independent of a rather technical formalism of branching programs. This condition proves to be sufficient in a sense that any rich set extended with all strings within Hamming distance of 3 is a hitting set for width-3 1-branching programs that are weakly oblivious (i.e. at each level where only one node branches to its two different successors, all nodes are labeled with the same variable). Then, we prove that any almost $O(\log n)$-wise independent set satisfies the richness condition. By using such a set due to Alon et al. (1992) our result provides an explicit polynomial time construction of a hitting set for (weakly oblivious) read-once branching programs of width 3 with acceptance probability $\varepsilon>\sqrt{12/13}$.
We have somewhat improved our presentation, updated references, and fixed some minor inconsistencies. The main revision concerns the disjointness of partition classes in the sufficiency proof for which the assumption that the branching program is read-once has appeared to be insufficient in one rather specific case. Therefore, we have introduced a notion of a `weakly oblivious' branching program, which solves the problem although we believe that this assumption is too strong and could be removed. Nevertheless, the full obliviousness of branching programs is widely (or implicitly) assumed in the context of pseudorandom generators.
The relationship between deterministic and probabilistic computations is one of the central issues in complexity theory. This problem can be tackled by constructing polynomial time hitting set generators which, however, belongs to the hardest problems in computer science even for severely restricted computational models. In our work, we consider read-once branching programs for which such a construction has been known only in the case of width 2. We characterize the hitting sets for read-once branching programs of width 3 by a necessary and (in a certain sense) sufficient so-called richness condition which is independent of a notion of branching programs. Then, we prove that any almost $(C\log n)$-wise independent set satisfies this richness condition for a suitable constant $C$. By using such a set due to Alon et al. (1992), our result provides an explicit polynomial time construction of a hitting set for read-once branching programs of width 3.
The main result, that the support of every almost $C \log n$-wise independent distribution is a hitting set for width-3 read once branching programs, cannot be correct.
Consider the uniform distribution over strings that have an odd number of zeroes: this is a $(n-1)$-wise independent distribution, but its support is not a hitting set generator for width-3 (and, in fact, not even width-2) branching programs.
We don't claim that any $C\log n$-wise independent set itself is a hitting set for width-3 read-once branching programs (Theorem 3 only says that such a set is "rich") but we extend such sets with all strings within Hamming distance of 3 (see Theorem 2). This makes a big difference. For example, a set with a single string extended with all strings within Hamming distance of 1 is an $\epsilon$-hitting set for width-2 read-once branching programs for $\epsilon>3/4$.
The assumption of Theorem 2 that 1-branching programs of width 3 need to be weakly oblivious can indeed be removed (cf. Footnotes 1 and 2 on p. 3 and p. 15, respectively). It follows from equations (64) and (65) that Theorem 3 holds for a stronger richness condition (cf. the original definition on p. 5): $A\subseteq\{0,1\}^*$ is strongly $\varepsilon$-rich if for sufficiently large $n$, for any index set $I\subseteq\{1,\ldots,n\}$, and for any partition $\{R_{1},\ldots,R_{r}\}$ of $I$ (where $r\geq 0$) the following implication holds: If $\prod_{j=1}^r(1-1/2^{|R_j|})\geq\varepsilon$, then for any $c\in\{0,1\}^n$ and for any $Q\subseteq\{1,\ldots,n\}\setminus I$ satisfying $|Q|\leq\log n$ there exists $a\in A\cap\{0,1\}^n$ such that $a_i=c_i$ for every $i\in Q$, and for every $j\in\{1,\ldots,r\}$ there exists $i\in R_j$ such that $a_i\not=c_i$.
This stronger richness condition can then be employed in the proof of Theorem 2 for non-oblivious width-3 1-branching programs as follows. Since (non-oblivious) $P$ is read-once, the classes $R_b$ (see the definition in Paragraph 5.1) are pairwise disjoint for different blocks $b$ except for the special case of $m_{b-1}=\nu_b$ for non-empty block $b>1$. In this special case, we know $q_b=0$ (i.e. no $Q_{bj}$ is defined for block $b$) and either $t_{12}^{(m_{b-1})}=t_{32}^{(m_{b-1})}=\frac{1}{2}$ and $t_{33}^{(m_{b-1})}=1$ if $\gamma_b=\nu_b$ or $t_{13}^{(m_{b-1})}=t_{33}^{(m_{b-1})}=\frac{1}{2}$ and $t_{32}^{(m_{b-1})}=1$ if $\gamma_b<\nu_b$ (cf. the sentence following equation (31) on p. 19). Thus, index $i\in R_b$ of the variable that is tested either at node $v_2^{(m_{b-1}-1)}$ if $\gamma_b=\nu_b$ or at node $v_3^{(m_{b-1}-1)}$ if $\gamma_b<\nu_b$ may possibly be included also in $R_{b-1}$. In order to secure that $R_b$ and $R_{b-1}$ are disjoint we redefine $R_b'=R_b\setminus\{i\}$ in this special case, which replaces $|R|$ with $|R|+1$ in equation (32) while inequality (37) remains still valid. This ensures that the classes $R_b$ are pairwise disjoint also for non-oblivious $P$.
For the recursive step in Paragraph 7.2, the stronger richness condition for $Q=\emptyset$ coincide with the original one. In the end of recursion (Section 8), on the other hand, inequality (61) ensures there is $Q=Q_{b^*j^*}$ for some $b^*\in\{1,\ldots,r+1\}$ and $j^*\in\{1,\ldots,q_{b^*}\}$ such that $|Q|\leq\log n$ according to (64), and the stronger richness condition can be employed for $Q$ and $R_1,\ldots,R_{b^*-1}$ according to (40), provided that $R_b\cap Q=\emptyset$ for every $b=1,\ldots,b^*-1$. This disjointness follows from the fact that $P$ is read-once except for the special case of $R_{b^*-1}\cap Q=\emptyset$ for $j^*=1$, $\kappa_{b^*1}=\sigma_{b^*1}=m_{b^*-1}$, and $t_{23}^{(m_{b^*-1})}=0$ (see the definition of $Q$ in Paragraph 5.2). In this particular case, however, it clearly suffices to use the stronger richness condition for $R_1,\ldots,R_{b^*-2}$ and $Q$.
