Abstract:
A regular $(1,+k)$-branching program ($(1,+k)$-ReBP) is an ordinary branching program with the following restrictions: (i) along every consistent path at most $k$ variables are tested more than once, (ii) for each node $v$ on all paths from the source to $v$ the same set $X(v)\subseteq X$ of variables is tested, and (iii) on each path from the source to a sink all variables $X$ are tested. We show that polynomial size $(1,+1)$-ReBP-s are more powerful than polynomial size read-once branching programs and that polynomial size $(1,+(k+1))$-ReBP-s are more powerful than polynomial size $(1,+k)$-ReBP-s. We prove lower bound $2^{(n-k)/2-k\log (n^2/k)}/2\sqrt{n}$ for $k=o(n^2)$ on the size of any nondeterministic $(1,+k)$-ReBP computing permutation function $PERM_{n^2}$ on $n^2$ arguments. The proof is based on combination of decomposing of $(1,+k)$-ReBP with communication complexity technique.