Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

Revision #2 to TR10-088 | 23rd November 2010 22:30

A Polynomial Time Construction of a Hitting Set for Read-Once Branching Programs of Width 3

RSS-Feed




Revision #2
Authors: Jiri Sima, Stanislav Zak
Accepted on: 23rd November 2010 22:30
Downloads: 854
Keywords: 


Abstract:

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}$.



Changes to previous version:

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).


Revision #1 to TR10-088 | 3rd November 2010 14:46

A Polynomial Time Construction of a Hitting Set for Read-Once Branching Programs of Width 3





Revision #1
Authors: Jiri Sima, Stanislav Zak
Accepted on: 3rd November 2010 14:46
Downloads: 756
Keywords: 


Abstract:

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}$.



Changes to previous version:

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.


Paper:

TR10-088 | 17th May 2010 15:16

A Polynomial Time Construction of a Hitting Set for Read-Once Branching Programs of Width 3





TR10-088
Authors: Jiri Sima, Stanislav Zak
Publication: 21st May 2010 20:33
Downloads: 1308
Keywords: 


Abstract:

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.


Comment(s):

Comment #1 to TR10-088 | 22nd May 2010 23:33

Read-once branching program and bounded independence

Authors: Luca Trevisan
Accepted on: 22nd May 2010 23:33
Keywords: 


Comment:

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.


Comment #2 to TR10-088 | 23rd May 2010 16:11

reply to Luca Trevisan's comment

Authors: Jiri Sima
Accepted on: 23rd May 2010 16:11
Keywords: 


Comment:

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$.


Comment #3 to TR10-088 | 23rd January 2011 14:22

The Hitting Set Construction Holds for NON-OBLIVIOUS Read-Once Branching Programs of Width 3





Comment #3
Authors: Jiri Sima
Accepted on: 23rd January 2011 14:22
Downloads: 802
Keywords: 


Abstract:

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$.




ISSN 1433-8092 | Imprint