ECCC-Report TR10-088https://eccc.weizmann.ac.il/report/2010/088Comments and Revisions published for TR10-088en-usSun, 23 Jan 2011 14:22:10 +0200
Comment 3
| The Hitting Set Construction Holds for NON-OBLIVIOUS Read-Once Branching Programs of Width 3 |
Jiri Sima
https://eccc.weizmann.ac.il/report/2010/088#comment3The 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$.
Sun, 23 Jan 2011 14:22:10 +0200https://eccc.weizmann.ac.il/report/2010/088#comment3
Revision 2
| A Polynomial Time Construction of a Hitting Set for Read-Once Branching Programs of Width 3 |
Jiri Sima,
Stanislav Zak
https://eccc.weizmann.ac.il/report/2010/088#revision2The 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}$.Tue, 23 Nov 2010 22:30:05 +0200https://eccc.weizmann.ac.il/report/2010/088#revision2
Revision 1
| A Polynomial Time Construction of a Hitting Set for Read-Once Branching Programs of Width 3 |
Jiri Sima,
Stanislav Zak
https://eccc.weizmann.ac.il/report/2010/088#revision1The 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}$.Wed, 03 Nov 2010 14:46:45 +0200https://eccc.weizmann.ac.il/report/2010/088#revision1
Comment 2
| reply to Luca Trevisan's comment |
Jiri Sima
https://eccc.weizmann.ac.il/report/2010/088#comment2We 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$.Sun, 23 May 2010 16:11:41 +0300https://eccc.weizmann.ac.il/report/2010/088#comment2
Comment 1
| Read-once branching program and bounded independence |
Luca Trevisan
https://eccc.weizmann.ac.il/report/2010/088#comment1The 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.Sat, 22 May 2010 23:33:52 +0300https://eccc.weizmann.ac.il/report/2010/088#comment1
Paper TR10-088
| A Polynomial Time Construction of a Hitting Set for Read-Once Branching Programs of Width 3 |
Jiri Sima,
Stanislav Zak
https://eccc.weizmann.ac.il/report/2010/088The 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.Fri, 21 May 2010 20:33:39 +0300https://eccc.weizmann.ac.il/report/2010/088