A Lower Bound Technique for Restricted Branching Programs and Applications

(Extended Abstract)

Philipp Woelfel^{⋆}

FB Informatik, LS2, Univ. Dortmund, 44221 Dortmund, Germany

                woelfel@Ls2.cs.uni-dortmund.de

Abstract. We present a new lower bound technique for two types of restricted Branching Programs (BPs), namely for read-once BPs (BP1s) with restricted amount of nondeterminism and for (1, +k)-BPs. For this technique, we introduce the notion of (strictly) k-wise l-mixed Boolean functions, which generalizes the concept of l-mixedness defined by Jukna in 1988 [3]. We prove that if a Boolean function f ∈ B_{n} is (strictly) k-wise l-mixed, then any nondeterministic BP1 with at most k − 1 nondeterministic nodes and any (1, +k)-BP representing f has a size of at least 2^{Ω(l)}. While leading to new exponential lower bounds of well-studied functions (e.g. linear codes), the lower bound technique also shows that the polynomial size hierarchy for BP1s with respect to the available amount of nondeterminism is strict. More precisely, we present a class of functions g_{n}^{k} ∈ B_{n} which can be represented by polynomial size BP1s with k nondeterministic nodes, but require superpolynomial size if only k − 1 nondeterministic nodes are available (for k = o(n^{1/3}/ log^{2/3} n)). This is the first hierarchy result of this kind where the BP1 does not obey any further restrictions. We also obtain a hierarchy result with respect to k for (1, +k)-BPs as long as k = o(\sqrt{n/ log n}). This extends the hierarchy result of Savický and Žák [9], where k was bounded above by \frac{1}{2} n^{1/6}/ log^{1/3} n.

1 Introduction and Results

Branching Programs (BPs) or equivalently Binary Decision Diagrams (BDDs) belong to the most important nonuniform models of computation. Deterministic and nondeterministic BPs can be simulated by the corresponding Turing machines, and the BP complexity of a Boolean function is a measure for the space complexity of the corresponding model of sequential computation. Therefore, one is interested in large lower bounds for BPs.

Definition 1. A (deterministic) Branching Program (short: BP) on the variable set X_{n} = {x_{1}, …, x_{n}} is a directed acyclic graph with one source and two sinks. The internal nodes are marked with variables in X_{n} and the sinks are

⋆ Supported in part by DFG grant We 1066/10-1.

labeled with the Boolean constants 0 and 1. Further, each internal node has two outgoing edges, marked with 0 and 1, respectively. A nondeterministic (short: n.d.) Branching Program is a BP with some additional unmarked nodes with outdegree two, called nondeterministic nodes. The size of a (possibly n.d.) Branching Program G is the number of its nodes, and ist denoted by |G|.

Let G be a (possibly n.d.) BP on X_{n} and a = (a_{1}, …, a_{n}) ∈ {0, 1}^{n} an assignment to the variables in X_{n}. A source-to-sink path in G is called computation path of a, if it leaves any node marked with x_{i} over the edge labeled with a_{i}. Note that an input may have multiple computation paths if G is n.d.

Let B_{n} denote the set of Boolean functions {0, 1}^{n} → {0, 1}. The BP G represents the function f ∈ B_{n} for which f(a) = 1 if and only if there exists a computation path of a leading to the 1-sink.

Until today, no superpolynomial lower bounds for general BPs representing an explicitly defined function are known. Therefore, various types of restricted BPs have been investigated, and one is interested in refining the proof techniques in order to obtain lower bounds for less restricted BPs. For this paper, the following two common types of restricted BPs are most important (for an indepth discussion of other restricted BP models we refer to [13]).

Definition 2. (i) A (n.d.) read-k-times BP (short: BPk) is a (n.d.) BP where

each variable appears on each computation path at most k times. (ii) A (n.d.) (1, +k)-BP is a (n.d.) BP where for each computation path p there

exist at most k variables appearing on p more than once.

Especially deterministic BP1s have been studied to a great extent. The first exponential lower bounds date back to the 80s [12, 14], and today, lower bounds for explicitly defined functions in P are as large as 2^{n−O(log^{2} n)} [1].

If one considers BPs which allow multiple tests of the same variable during a computation, then one has to distinguish between syntactic and semantic restrictions. The restrictions given in the definition above are semantic, because they have to hold on each computation path. But since graph theoretical paths may be inconsistent, one may obtain BPs with less computational power if the restriction has to hold even on each graph theoretical path. Such restrictions are called syntactic, and the BPs corresponding to Definition 2 but with syntactic restrictions are called syntactic BPks and syntactic (1, +k)-BPs, respectively.

Besides the general interest in finding exponential lower bounds for less and less restricted BP-models, much of the research on Branching Programs has focused on separating the power of different types of Branching Programs. Similarly, it has been of considerable interest, how the computational power of BPs is influenced by e.g. the available amount of nondeterminism or the multiplicity of variable tests (i.e. the term k in BPks or (1, +k)-BPs).

Results on the influence of the available amount of nondeterminism have so far been obtained only for n.d. BP1s with additional restrictions.

Definition 3. (i) An (∨, k)-BP1 is a family of k deterministic BP1s and represents the function f_{1} ∨ … ∨ f_{k}, where f_{i} is the function represented by the ith BP1.

(ii) A BP1 is called Ordered Binary Decision Diagram (short: OBDD), if the nodes can be partitioned into levels such that all edges point only from lower to higher levels and all internal nodes of one level are marked with the same variable. A k-Partitioned Binary Decision Diagram (short: k-PBDD) is an (∨, k)-BP1 whose BP1s are in fact OBDDs.

Note that we can regard an (∨, k)-BP1 as a n.d. BP1 having a binary tree of exactly k − 1 n.d. nodes at the top such that the outgoing edges of the leaves lead to the sources of k disjoint BP1s. Hence, the set of functions which can be represented in polynomial size by (∨, k)-BP1s is a subset of the functions which can be represented in polynomial size by BP1s with at most k − 1 n.d. nodes. Although not yet proven, the results of [5] indicate that (∨, k)-BP1s might be in fact less powerful than n.d. BP1s with k − 1 nondeterministic nodes.

Bollig and Wegener [2] have proven the first hierarchy result for k-PBDDs with respect to k, which has been extended later by Sauerhoff [6]. He presented functions being representable by polynomial size (k + 1)-PBDDs but requiring superpolynomial size k-PBDDs if k = O((n/ log^{1+ϵ} n)^{1/4}) for arbitrary ϵ > 0. This means that for these k, the polynomial size hierarchy of k-PBDDs with respect to k is strict. A generalization of this result was obtained by Savický and Sieling [7], who proved that the polynomial size hierarchy of (∨, k)-BP1s with respect to k ist strict for k ≤ 2/3\sqrt{log n}.

One of the main contributions of this paper is a hierarchy result for n.d. BP1s without any restrictions except on the number of n.d. nodes. We present a class of multipointer functions g_{n}^{k} ∈ B_{n}, which can be represented by polynomial size n.d. BP1s having k n.d. nodes, but require superpolynomial size if at most k − 1 n.d. nodes are available (for k = o(n^{1/3}/ log^{2/3} n)).

The other main contribution of this paper is an improved hierarchy result for (1, +k)-BPs with respect to k. For syntactic (1, +k)-BPs, the first hierarchy result was obtained by Sieling in 1996 [10] and later improved as well as generalized for the semantic restriction by Savický and Žák [9]. They showed that the polynomial size hierarchy with respect to k is strict for (1, +k)-BPs if k ≤ \frac{1}{2}n^{1/6}/ log^{1/3} n and for syntactic (1, +k)-BPs if k ≤ \frac{1}{2} \sqrt{n}/ log n. We extend their result for both types of restrictions by presenting a class of functions for which polynomial size syntactic (1, +k)-BPs but no polynomial size (semantic) (1, +(k − 1))-BPs exist if k = o(\sqrt{n/ log n}).

The hierarchy results for n.d. BP1s and (1, +k)-BPs are possible because of a new lower bound technique. Interestingly enough, this technique can be equivalently applied for both types of BPs. It mainly consists of introducing the notion of strictly k-wise l-mixed functions, and of proving for such functions a lower bound of 2^{l} + 1 for n.d. BP1s with at most k − 1 n.d. nodes and a lower bound of 2^{l/2} for (1, +k)-BPs. This will be done in Section 3. In Section 4, we will show how to prove the k-wise l-mixedness of functions. As an easy example, we show that d-rare m-dense functions, investigated e.g. by Jukna and Razborov [4], are in fact k-wise l-mixed for l < min {d, m/k}. We obtain as a corollary exponential lower bounds for linear codes in the (1, +k)-BP model, which have already been proven in [4], and new exponential lower bounds in the n.d. BP1 model with restricted amount of nondeterminism. We also show how to construct easily from a 1-wise l-mixed function in B_{n} a k-wise l/k-mixed function in B_{kn}. This construction helps us in Section 5 to obtain the hierarchy result for (1, +k)- BPs. The hierarchy result for n.d. BP1s will finally be stated in Section 6.

2 Notation

In the following text, we consider functions defined on the n Boolean variables in X_{n} = {x_{1}, …, x_{n}}. A partial input is an element α = (α^{1}, …, α^{n}) ∈ {0, 1, ∗}^{n}. While a position α^{i} with value 0 or 1 means that the input variable x_{i} is fixed to the corresponding constant, a value of ∗ means that the input variable remains free. If f ∈ B_{n} is a Boolean function and α is a partial input, then f|_{α} means the subfunction of f obtained by restricting all inputs to α. For a partial input α ∈ {0, 1, ∗}^{n}, we denote the support of α by S(α) := {x_{i} | α^{i} ≠ ∗}. The empty partial input, i.e. the partial input with support ∅, is written as ε. For two partial inputs α, β with the same support, we let D(α, β) be the set which contains all variables x_{i} ∈ X_{n} for which α^{i} ≠ β^{i}. If α and β are partial inputs with disjoint supports, then we denote by αβ the partial input where (αβ)^{i} equals α^{i} or β^{i} if x_{i} is an element of S(α) or S(β), respectively, and equals ∗ if x_{i} ∉ S(α) ∪ S(β).

3 The Lower Bound Technique

Our lower bound technique relies mainly on a generalization of the following property of Boolean functions, which was defined by Jukna in 1988 [3].

Definition 4. Let l ∈ ℕ. A function f ∈ B_{n} is called l-mixed, if for all V ⊆ X_{n} such that |V | = l, any two distinct partial inputs α, β with support V yield different subfunctions, i.e. f|_{α} ≠ f|_{β}.

Many exponential lower bound proofs for BP1s use the following folklore fact.

Proposition 1. The size of any BP1 for an l-mixed function is at least 2^{l} + 1.

The following definition generalizes the above definition of l-mixed functions and is fundamental for our lower bound technique.

Definition 5. Let kl ≤ n. In the following formula, we restrict the choices of W_{1}, …, W_{k}, V_{1}, …, V_{k} to disjoint subsets of X_{n} such that |V_{j}| = l ( 1 ≤ j ≤ k). The choices of the partial inputs λ_{j}, α_{j}, β_{j} are restricted in such a way that S(λ_{j}) = W_{j} and S(α_{j}) = S(β_{j}) = V_{j}. Below, we allow for each 1 ≤ j ≤ k the choice of a partial assignment γ_{j} ∈ {α_{j}, β_{j}}. We then denote by γ_{j}^{∗} the element in {α_{j}, β_{j}}\γ_{j} and let c = λ_{1}γ_{1} … λ_{k}γ_{k} and c_{j} be the partial assignment obtained from c by replacing γ_{j} with γ_{j}^{∗}.

A Boolean function f ∈ B_{n} is called k-wise l-mixed if

∃W_{1}, λ_{1} ∀V_{1}, α_{1} ≠ β_{1} ∃γ_{1} ∈ {α_{1}, β_{1}} … ∃W_{k}, λ_{k} ∀V_{k}, α_{k} ≠ β_{k} ∃γ_{k} ∈ {α_{k}, β_{k}} :

∑_{i=1}^{k} |W_{i}| ≤ n − kl ∧ ∃x^{∗} ∀1 ≤ j ≤ k : f|_{c}(x^{∗}) ≠ f|_{c_{j}}(x^{∗}),

where x^{∗} is an input for the subfunction f|_{c} (and f|_{c_{j}}), i.e. S(x^{∗}) = X_{n} \ (W_{1} ∪ V_{1} ∪ … ∪ W_{k} ∪ V_{k}). If in the above formula we even have f|_{c}(x^{∗}) > f|_{c_{j}}(x^{∗}) (instead of “ ≠”), then f is called strictly k-wise l-mixed.

Remark 1. Any strictly k-wise l-mixed function is k-wise l-mixed. Furthermore, any (strictly) (k +1)-wise (l +1)-mixed function is (strictly) k-wise (l +1)-mixed and also (strictly) (k + 1)-wise l-mixed. Finally, a function f is 1-wise l-mixed if and only if there exists an l-mixed subfunction of f.

The property k-wise l-mixed of a Boolean function implies lower bounds for (1, +k)-BPs as well as for n.d. BP1s with limited amount of nondeterminism. In order to measure the amount of nondeterminism in BPs, we need an appropriate measurement. Here, we choose the number of n.d. nodes, but another possibility would be to count the maximum number of n.d. nodes on any computation path. The proof of the following theorem though, can be adapted in order to obtain similar results for other measures of nondeterminism.

Theorem 1. (a) If f ∈ B_{n} is a strictly k-wise l-mixed function and G is a n.d.

BP1 with at most k − 1 n.d. nodes representing f, then |G| ≥ 2^{l} + 1.

(b) If f ∈ B_{n} is a k-wise l-mixed function and G is a (1, +(k − 1))-BP representing f, then |G| ≥ 2^{l/2}.

Note that the (1, +k)-restriction is semantic in this case.

Due to space restrictions, we only prove part (a) of the theorem. In order to do so, we make use of the notion of filters and of the idea behind a lower bound technique of Simon and Szegedy [11] for deterministic BP1s. A filter of a set X is a closed upward subset of 2^{X} (i.e. if S ∈ F, then all supersets of S are in F). Let F be a filter of X_{n}. A subset B ⊆ X_{n} is said to be in the boundary of F if B ∉ F but B ∪ {x_{i}} ∈ F for some x_{i} ∈ X_{n}.

Let p be a path starting at the source of a n.d. BP1 and leading to an arbitrary edge e = (v, w). We say that a partial input α induces the path p, if no variable in S(α) is tested on any path from w to a sink and if α is consistent with p (i.e. for any c-edge of p, c ∈ {0, 1}, leaving a node marked with x_{i}, either α^{i} = c or α^{i} = ∗).

Lemma 1. Let G be a (possibly n.d.) BP1 on X_{n}. For each filter F of X_{n} there exists a set B in the boundary of F for which at least ⌈2^{|\overline{B}|}/(|G| − 1)⌉ different partial assignments with support \overline{B} (= X_{n} \ B) induce paths leading to the same edge.

The proof of this lemma is omitted, but it mainly adapts an idea of [11] to the nondeterministic model. We use it in the following proof of Theorem 1 (a).

Proof (of Theorem 1 (a)). In the following, we write f ≤ g for two functions f, g defined on the same domain, if f(x) ≤ g(x) for all inputs x.

The proof is by induction on k. If k = 1, then G contains no n.d. nodes and is deterministic. Then, upon choosing W_{1} and λ_{1} appropriately, f|_{λ_{1}} is an l-mixed subfunction of f (see Remark 1) and the claim follows from Proposition 1.

Let now k > 1 and G be a n.d. BP1 consisting of L ≤ 2^{l} nodes, of which at most k − 1 are nondeterministic. We assume w.l.o.g. that each n.d. node in G has two different successors (if this is not the case, we may replace the n.d. node with its successor). We show that if G computes the function f, then

∀W_{1}, λ_{1} ∃V_{1}, α_{1} ≠ β_{1} ∀γ_{1} ∈ {α_{1}, β_{1}} … ∀W_{k}, λ_{k} ∃V_{k}, α_{k} ≠ β_{k} ∀γ_{k} ∈ {α_{k}, β_{k}} :

∑_{i=1}^{k} |W_{i}| > n − kl ∨ f|_{c} ≤ ⋁_{j=1}^{k} f|_{c_{j}}, (1)

where c and c_{j} are defined as in Definition 5. Hence, f is not strictly k-wise l-mixed.

Let first W_{1} ⊆ X_{n} as well as a partial input λ_{1} with support W_{1} be chosen arbitrarily. We may assume that |W_{1}| ≤ n − kl, since otherwise there is nothing to prove. Consider the restricted n.d. BP1 G|_{λ_{1}} representing the function f|_{λ_{1}} on the variables in X′ = X_{n} \ W_{1} and note that n′ := |X′| ≥ kl. We define a filter F on X′.

F := {V ⊆ X′ | |V | > n′ − l}.

Each set B in the boundary of F has a cardinality of n′ − l, and hence |\overline{B}| = l (note that \overline{B} = X′ \ B in this case). Because of Lemma 1, there exists a set B in the boundary of F such that at least ⌈2^{|\overline{B}|}/(L − 1)⌉ ≥ ⌈2^{l}/(2^{l} − 1)⌉ = 2 distinct partial assignments with support \overline{B} induce paths leading to the same edge (v, w). We let V_{1} = \overline{B} and α_{1} ≠ β_{1} be two such partial assignments with support V_{1}. Note that |V_{1}| = l. Finally, let γ_{1} be chosen arbitrarily among α_{1} and β_{1}. Let f_{w} be the subfunction defined by the (possibly n.d.) BP1 rooted at node w. All 1-inputs for f_{w} obviously are also 1-inputs for f_{λ_{1}γ_{1}} and f_{λ_{1}γ_{1}^{∗}}, because the inputs γ_{1} and γ_{1}^{∗} both induce paths leading to the edge (v, w) in G|_{λ_{1}}. Hence,

f_{w} ≤ f|_{λ_{1}γ_{1}}, f|_{λ_{1}γ_{1}^{∗}}.  (2)

Now let p be the path induced by the partial input γ_{1}, leading from the source of G|_{λ_{1}} to the edge (v, w). If there is no n.d. node on p, then f|_{λ_{1}γ_{1}} = f_{w} and thus f|_{λ_{1}γ_{1}} ≤ f|_{λ_{1}γ_{1}^{∗}} by (2). No matter how the choice of the remaining W_{i}, λ_{i}, V_{i}, α_{i}, β_{i}, γ_{i} will be, statement (1) is fulfilled.

Therefore, we assume that there is at least one n.d. node on the path p. Let u be the last n.d. node on this path and let (u, u_{0}) and (u, u_{1}) be the two outgoing edges of u, where (u, u_{0}) is the edge on p. We replace the n.d. node u with the node u_{1} by redirecting all edges pointing to u in such a way that they point to u_{1}. Let f′ (= f′|_{λ_{1}}) be the function computed by the resulting Branching Program. Obviously

f′|_{λ_{1}} ≤ f|_{λ_{1}},  (3)

because following the (u, u_{0})-edge in the original BP1 G|_{λ_{1}} might only allow additional inputs to lead to the 1-sink. Furthermore, since u was the last n.d. node on the path from the source to (v, w) induced by the partial input γ_{1},

f|_{λ_{1}γ_{1}} = f′|_{λ_{1}γ_{1}} ∨ f_{w} ≤^{(2)} f′|_{λ_{1}γ_{1}} ∨ f|_{λ_{1}γ_{1}^{∗}}.  (4)

As a last step, we restrict the so obtained n.d. BP1 for the function f′|_{λ_{1}} to a n.d. BP1 G′ for the function f′|_{λ_{1}γ_{1}}. Note that G′ is of size smaller than 2^{l} and that f′|_{λ_{1}γ_{1}} is a function on n′′ = n − l − |W_{1}| ≥ (k − 1)l variables. Furthermore, since we have removed the n.d. node u from G|_{λ_{1}}, G′ contains at most k − 2 n.d. nodes. This means by the induction hypothesis that the subfunction f′|_{λ_{1}γ_{1}} is not strictly (k − 1)-wise l-mixed. In other words

∀W_{2}, λ_{2} ∃V_{2}, α_{2} ≠ β_{2} ∀γ_{2} ∈ {α_{2}, β_{2}} … ∀W_{k}, λ_{k} ∃V_{k}, α_{k} ≠ β_{k} ∀γ_{k} ∈ {α_{k}, β_{k}} :

∑_{i=2}^{k} |W_{i}| > n′′ − (k − 1)l ∨ (f′|_{λ_{1}γ_{1}})|_{c′} ≤ ⋁_{j=2}^{k} (f′|_{λ_{1}γ_{1}})|_{c′_{j}},

where c′ is the partial input λ_{2}γ_{2} … λ_{k}γ_{k} and c′_{j} is obtained from c′ by replacing γ_{j} with γ_{j}^{∗}.

Assume first that ∑_{i=2}^{k} |W_{i}| > n′′ − (k − 1)l. Because n′′ equals n − l − |W_{1}| it follows that ∑_{i=1}^{k} |W_{i}| > n − kl, and property (1) is fulfilled. Therefore, we assume ∑_{i=2}^{k} |W_{i}| ≤ n′′ − (k − 1)l and hence

(f′|_{λ_{1}γ_{1}})|_{c′} ≤ ⋁_{j=2}^{k} (f′|_{λ_{1}γ_{1}})|_{c′_{j}}.  (5)

Altogether we obtain

f|_{c} = f|_{λ_{1}γ_{1}...λ_{k}γ_{k}} = (f|_{λ_{1}γ_{1}})|_{λ_{2}γ_{2}...λ_{k}γ_{k}}
≤^{(4)} (f′|_{λ_{1}γ_{1}})|_{λ_{2}γ_{2}...λ_{k}γ_{k}} ∨ (f|_{λ_{1}γ_{1}^{∗}})|_{λ_{2}γ_{2}...λ_{k}γ_{k}}
≤^{(5)} ( ⋁_{j=2}^{k} (f′|_{λ_{1},γ_{1}})|_{λ_{2}...λ_{k}γ_{2}...γ_{j−1}γ_{j}^{∗}γ_{j+1}...γ_{k}}) ∨ (f|_{λ_{1}γ_{1}^{∗}})|_{λ_{2}γ_{2}...λ_{k}γ_{k}}

≤^{(3)} ( ⋁_{j=2}^{k} (f|_{λ_{1}γ_{1}})|_{λ_{2}...λ_{k}γ_{2}...γ_{j−1}γ_{j}^{∗}γ_{j+1}...γ_{k}}) ∨ (f|_{λ_{1}γ_{1}^{∗}})|_{λ_{2}γ_{2}...λ_{k}γ_{k}}

= ⋁_{j=1}^{k} f|_{λ_{1}...λ_{k}γ_{1}...γ_{j−1}γ_{j}^{∗}γ_{j+1}...γ_{k}} = ⋁_{j=1}^{k} f|_{c_{j}}.

Hence, we have proven (1). ⊓ ⊔

4 Applications

4.1 Linear Codes and d-rare m-dense Functions

As a first application of our lower bound technique, we consider d-rare m-dense functions, which have been investigated e.g. by Savický and Žák [8] and by Jukna and Razborov [4]. Such functions have been known to be hard for (1, +k) BPs and our proof method now demonstrates that they are also hard for n.d. BP1s, if not enough nondeterminism is available.

Definition 6. A function f ∈ B_{n} is called d-rare if any two different inputs a, b ∈ f^{−1}(1) have a Hamming distance of at least d (i.e. |D(a, b)| ≥ d). The function f is called m-dense if |S(α)| ≥ m for any partial input α with f|_{α} = 0.

Theorem 2. Any d-rare m-dense function is strictly k-wise l-mixed for l < min {d, m/k}.

Proof. This proof is simple, because we do not need to bother about the choice of W_{i}, λ_{i} or γ_{i} for 1 ≤ i ≤ k. We simply choose W_{i} = ∅, λ_{i} = ε and upon some arbitrarily given α_{i} ≠ β_{i} with support V_{i} (|V_{i}| = l) we choose γ_{i} = α_{i}. Then we consider the partial input c = λ_{1}γ_{1} … λ_{k}γ_{k} and the inputs c_{j} which are obtained from c by replacing γ_{j} with γ_{j}^{∗}. Since f is m-dense and S(c) ≤ kl < m by construction, we know that the subfunction f|_{c} has an input x^{∗} such that f|_{c}(x^{∗}) = 1. For this x^{∗} on the other hand, the complete inputs cx^{∗} and c_{j}x^{∗} have a Hamming distance of |D(c, c_{j})| ≤ l < d. Therefore, the d-rareness of f implies f|_{c_{j}}(x^{∗}) ≠ 1 for all 1 ≤ j ≤ k. ⊓ ⊔

Corollary 1. Any n.d. BP1 with at most k n.d. nodes or any (1, +k)- BP representing a d-rare m-dense function has a size of at least min {2^{(d−1)/2}, 2^{⌊(m−1)/(k+1)⌋/2}}.

Note that the same result for (1, +k)-BPs was already obtained by Jukna and Razborov [4] with a different technique. The result for n.d. BP1s is new though. The authors of [4] also show that if C is a linear code over GF (2) with minimal distance d_{1} and if C^{⊥} is its dual with minimal distance d_{2}, then the characteristic function of C is d_{1}-rare and d_{2}-dense. This leads to a lower bound of min {2^{(d_{1}−1)/2}, 2^{⌊(d_{2}−1)/(k+1)⌋/2}} for n.d. BP1s with at most k n.d. nodes and for (1, +k)-BPs representing such a linear code. We only state one corollary for Reed-Muller codes, which follows instantly from the discussion in [4] and was stated there for (1, +k)-BPs.

Corollary 2. Let R(r, ℓ) be the rth order binary Reed-Muller code of length n = 2^{ℓ}. Let further 0 ≤ k ≤ n and r = ⌊1/2(ℓ + log(k + 1))⌋. Then any (1, +k)- BP and any n.d. BP1 with at most k n.d. nodes representing the characteristic

function of R(r, ℓ) has size at least 2^{Ω(\sqrt{n/(k+1)} )}.

4.2 Disjoint Conjunctions

We state now a theorem which describes how to obtain k-wise l-mixed functions from l-mixed ones. Let f be a function on variables in X_{n}. We consider the disjoint conjunction f^{k} with respect to f on the variables in X_{kn}, which is defined as follows. For x = (x_{1}, …, x_{kn}) ∈ {0, 1}^{kn} let f^{k}(x) = f_{1}(x)∧…∧f_{k}(x), where f_{i}(x) = f(x_{(i−1)n+1}, …, x_{in}).

Theorem 3. If f is (kl)-mixed, then f^{k} is strictly k-wise l-mixed.

The l-mixedness of a function f implies that f is hard to compute by BP1s or equivalently by (1, +0)-BPs. Hence, the above theorem leads to a generalization of this fact in the sense that the disjoint conjunction f^{k} of a (kl)-mixed function f is hard to compute for a (1, +(k − 1))-BP.

Proof. Let N = kn and let X_{i} be the set of variables on which f_{i} may depend, i.e. X_{i} = {x_{(i−1)n+1}, …, x_{in}}. We first choose W_{1} = ∅ and λ_{1} = ε. Then we consider a k-round game in which we play against an adversary who starts the ith round by choosing V_{i}, α_{i}, β_{i}, after which we are allowed to choose W_{i+1}, λ_{i+1}. We show that we can influence the game by our choices in such a way that after r ≤ k rounds the following situation is obtained for any j ∈ {1, …, r}.

(I1) The set W_{j+1} only consists of variables in X_{i_{j}} for some i_{j} ∈ {1, …, k} and

the indices i_{1}, …, i_{r} are all different. (I2) All variables in X_{i_{1}}, …, X_{i_{r}} are fixed by λ_{1}γ_{1} … λ_{r}γ_{r}λ_{r+1}, i.e.

X_{i_{1}} ∪ … ∪ X_{i_{r}} ⊆ W_{1} ∪ V_{1} ∪ … ∪ W_{r} ∪ V_{r} ∪ W_{r+1}. (I3) In each X_{i}, i ∉ {i_{1}, …, i_{r}}, there are at most rl variables fixed. (I4) f_{i_{j}}|_{λ_{1}γ_{1}...λ_{j}γ_{j}λ_{j+1}} = 1 and f_{i_{j}}|_{λ_{1}γ_{1}...λ_{j}γ_{j}^{∗}λ_{j+1}} = 0.

Assume that we have played the game k rounds in such a way that (I1)-(I4) are fulfilled for r = k. Because all indices i_{1}, …, i_{k} are different (I1), and all variables in X_{i_{1}}, …, X_{i_{k}} are fixed (I2), the assignment λ_{1}γ_{1} … λ_{k}γ_{k}λ_{k+1} forms a complete input for f^{k}. We let x^{∗} = λ_{k+1} and c, c_{j} as in Definition 5. Then property (I4) implies on one hand that f^{k}|_{c}(x^{∗}) = 1, while on the other for each 1 ≤ j ≤ k it follows from f_{i_{j}}|_{c_{j}}(x^{∗}) = 0 that f^{k}|_{c_{j}}(x^{∗}) = 0. Furthermore, by property (I1) each of the sets W_{2}, …, W_{k} contains at most n variables. Since in addition W_{1} = ∅, we have ∑_{i=1}^{k} |W_{i}| ≤ (k − 1)n = N − n ≤ N − kl. For the last inequality we have used kl ≤ n, which follows from the (kl)-mixedness of f. Altogether, the conditions of Definition 5 showing that f^{k} is strictly k-wise l-mixed are fulfilled.

Therefore, it suffices to show that we can play the game for k rounds such that after each round (I1)-(I4) hold. This is trivially true after 0 rounds, and we show now the claim for the (r + 1)th round (1 ≤ r + 1 ≤ k).

Let the adversary choose V_{r+1} and α_{r+1} ≠ β_{r+1}. Then there exists a variable x_{i} ∈ V_{r+1} which is fixed to different constants by α_{r+1} and β_{r+1}. Let i_{r+1} be the index for which x_{i} ∈ X_{i_{r+1}}. Note that i_{r+1} ∉ {i_{1}, …, i_{r}}, because by (I2) all variables in the sets X_{i_{1}}, …, X_{i_{r}} had been fixed in previous rounds and are therefore not contained in V_{r+1}.

Now we restrict the partial input λ_{1}γ_{1} … λ_{r}γ_{r}λ_{r+1}α_{r+1} to the variables in X_{i_{r+1}} and obtain a partial input α. In the same way, we obtain β by restricting λ_{1}γ_{1} … λ_{r}γ_{r}λ_{r+1}β_{r+1} to the variables in X_{i_{r+1}}. Obviously, S(α) = S(β) and by our choice of X_{i_{r+1}}, it is α ≠ β. Furthermore, using the fact that |V_{r+1}| = l, we know by (I3) that not more than (r + 1)l variables are fixed in X_{i_{r+1}}, hence |S(α)| = |S(β)| ≤ kl. Using the assumption that f is (kl)-mixed, this implies by Proposition 1 that f|_{α} ≠ f|_{β} (we assume here that the input variables for f are in X_{i_{r+1}} instead of in X_{n}). Thus, there exists an assignment y to the free variables in X_{i_{r+1}} as well as a choice γ ∈ {α, β} such that f|_{γ}(y) = 1 and f|_{γ^{∗}}(y) = 0. We finally let γ_{r+1} be the element in {α_{r+1}, β_{r+1}} which corresponds to the above choice of γ. Then obviously f_{i_{r+1}}|_{λ_{1}γ_{1}...λ_{r}γ_{r}λ_{r+1}γ_{r+1}}(y) = 1 and f_{i_{r+1}}|_{λ_{1}γ_{1}...λ_{r}γ_{r}λ_{r+1}γ_{r+1}^{∗}}(y) = 0. Hence, if we let λ_{r+2} := y and W_{r+2} = S(λ_{r+2}), then (I4) is fulfilled. Furthermore, by construction W_{r+2} only consists of variables in X_{i_{r+1}} and all variables in X_{i_{1}}, …, X_{i_{r+1}} are fixed. Therefore also (I1) and (I2) hold. Condition (I3) follows already from (I1) and (I2), because each of the assignments γ_{1}, …, γ_{r} fixes at most l variables and the assignments λ_{1}, …, λ_{r+1} fix only variables in X_{i}, i ∈ {i_{1}, …, i_{r}}. We have shown therefore, that there exists a playing strategy such that for any 0 ≤ r ≤ k after the rth round the conditions (I1)-(I4) are fulfilled. This proves the claim. ⊓ ⊔

5 Improving the Hierarchy for (1, +k)-BPs

We consider now the function weighted sum, which was used by Savický and Žák [9] in order to prove a hierarchy for (1, +k)-BPs.

Definition 7. For any positive integer n let p(n) be the smallest prime greater than n. The function WS_{n} ∈ B_{n} (called weighted sum) is defined by

WS_{n}(x) = \begin{cases}x_{s} & if s ∈ \{1, …, n\} \\ x_{1} & otherwise, \end{cases} where s = (∑_{i=1}^{n} ix_{i}) mod p(n).

Savický and Žák have shown that WS_{n} is l-mixed for large l, and have used this function in order to obtain a hierarchy for (1, +k)-BPs.

Theorem 4 ([9]). For any δ > 0 and any large enough n, the function WS_{n} is l-mixed for l = n − ⌊(2 + δ)\sqrt{n}⌋ − 2.

Theorem 5 ([9]). There exists a class of functions h_{n,k} ∈ B_{n} representable by polynomial-size (1, +k)-BPs but not by polynomial-size (1, +(k − 1))-BPs as long as k ≤ n^{1/6}/(log^{1/3} n).

It is obvious how to construct a syntactic (1, +1)-BP representing the function WS_{n} with at most O(n^{2}) nodes. On the other hand, Theorem 4 implies that any (1, +0)-BP (or equivalently any BP1) for WS_{n} has exponential size. We may now look at the disjoint conjunction f_{N,k} := (WS_{n})^{k} with respect to WS_{n}. Note that f_{N,k} is a function in N = kn variables. Furthermore, it is easy to see that f_{N,k} can be computed by a syntactic (1, +k)-BP of size O(kn^{2}) = O(N^{2}/k). But by Theorem 1 (b) and Theorem 3 we know that any (1, +(k − 1))-BP for f_{N,k} has a size of at least 2^{l/(2k)}, where l = n − ⌊(2 + δ)\sqrt{n}⌋ − 2 = Ω(n) = Ω(N/k). (for any δ and sufficiently large n). Hence, we get an improved hierarchy as described by the following corollary.

Corollary 3. The function f_{N,k} ∈ B_{N} can be represented by polynomial size syntactic (1, +k)-BPs but not by polynomial size (1, +(k − 1))-BPs for k =

o(\sqrt{N/ log N}).

6 A Hierarchy for BP1s with Restricted Amount of Nondeterminism

We finally develop a family of multipointer functions g_{n}^{k}, which can be easily computed in polynomial size by (k + 1)-PBDDs. On the other hand, for any BP1 having at most k −1 n.d. nodes, an exponential size is required. Recall that a (k + 1)-PBDD can be regarded as a restricted n.d. BP1 having exactly k n.d. nodes at the top.

The idea behind the following definition of g_{n}^{k} is inspired by the functions used by Savický and Sieling [7] for their hierarchy result for (∨, k)-BP1s. Let n and k be arbitrary integers such that k(k + 1) ≤ n/⌈log n⌉, and let b = ⌊n/(k(k + 1))⌋ and s = ⌊b/⌈log(kb)⌉⌋. We partition the n variables in X_{n} into k(k + 1) consecutive blocks B_{i,j} of size b, where i ∈ {0, …, k} and j ∈ {0, …, k − 1}, and possibly one block of the remaining variables. Each block B_{i,j} is then partitioned into ⌈log(kb)⌉ subblocks, each having either size s or size s + 1. The set of the input variables in the blocks B_{i,0}, …, B_{i,k−1} is called the sector S_{i} (0 ≤ i ≤ k) of the input and has cardinality kb. For the ease of notation, we enumerate the variables in such a way that the sector S_{i} contains the variables x_{i,0}, …, x_{i,kb−1}.

The function value of the function g_{n}^{k} is determined as follows. The majority of the setting of the s variables in each subblock of a block B_{i,j} determines a bit. The ⌈log(kb)⌉ bits obtained this way for a block B_{i,j} are interpreted as an integer in {0, …, 2^{⌈log(kb)⌉} − 1}, which is taken modulo kb such that a value p_{i,j} ∈ {0, …, kb − 1} is obtained. This value p_{i,j} points to the variable x_{i⊕j,p_{i,j}} in the sector S_{i⊕j}, where i ⊕ j := (i + j + 1) mod (k + 1). Let h_{i,j} be the function which computes the value of the input variable the pointer p_{i,j} points to, i.e. h_{i,j}(x) = x_{i⊕j,p_{i,j}}. Then

h_{i} := ⋀_{j=0}^{k−1} h_{i,j} and g_{n}^{k} := ⋁_{i=0}^{k} h_{i}.

Since the function g_{n}^{k} is the disjunction of k+1 functions h_{i}, a correct (k+1)- PBDD may consist of k +1 OBDDs, each representing a function h_{i} (0 ≤ i ≤ k). The idea behind constructing an OBDD which represents h_{i} is that the OBDD reads a block B_{i,j} of the sector S_{i}, determines the corresponding pointer p_{i,j} and finally may obtain the value of the function h_{i,j}. Depending on whether this value is 0 or 1, the OBDD stops with output 0 or continues this proceeding with the next block B_{i,j+1} in the sector S_{i}. A detailed discussion on how to construct such OBDDs with polynomial size will be available in the full version of this paper. Due to space restrictions we also omit the proof that the function g_{n}^{k} is k-wise l-mixed. The following theorem summarizes the upper and lower bounds for the function g_{n}^{k}.

Theorem 6. The functions g_{n}^{k} ∈ B_{n} can be represented by (k + 1)-PBDDs of size O(n^{3}/k^{3}) (and hence in polynomial size by n.d. BP1s with at most k n.d. nodes). On the other hand, any n.d. BP1 with at most k − 1 n.d. nodes has a size of at least 2^{Ω(n/(k^{3} log n))}, which is not polynomial for k = o(n^{1/3}/ log^{2/3} n).

Acknowledgment

I thank Beate Bollig, Martin Sauerhoff, Detlef Sieling and Ingo Wegener for proofreading and helpful comments.

References

1. A. Andreev, J. Baskakov, A. Clementi, and J. Rolim. Small pseudo-random sets yield hard functions: New tight explict lower bounds for branching programs. In Proceedings of the 26th International Colloquium on Automata, Languages, and Programming, vol. 1644 of Lecture Notes in Computer Science, pp. 179–189. 1999.

2. B. Bollig and I. Wegener. Complexity theoretical results on partitioned (nondeterministic) binary decision diagrams. Theory of Computing Systems, 32:487–503, 1999.

3. S. Jukna. Entropy of contact circuits and lower bounds on their complexity. Theoretical Computer Science, 57:113–129, 1988.

4. S. Jukna and A. Razborov. Neither reading few bits twice nor reading illegally helps much. Discrete Applied Mathematics, 85:223–238, 1998.

5. M. Sauerhoff. Computing with restricted nondeterminism: The dependence of the OBDD size on the number of nondeterministic variables. In Proceedings of the 19th Conference on Foundations of Software Technology and Theoretical Computer Science, vol. 1738 of Lecture Notes in Computer Science, pp. 342–355. 1999.

6. M. Sauerhoff. An improved hierarchy result for partitioned BDDs. Theory of Computing Systems, 33:313–329, 2000.

7. P. Savický and D. Sieling. A hierarchy result for read-once branching programs with restricted parity nondeterminism. In Mathematical Foundations of Computer Science: 25th International Symposium, vol. 1893 of Lecture Notes in Computer Science, pp. 650–659. 2000.

8. P. Savický and S. Žák. A lower bound on branching programs reading some bits twice. Theoretical Computer Science, 172:293–301, 1997.

9. P. Savický and S. Žák. A read-once lower bound and a (1, +k)-hierarchy for branching programs. Theoretical Computer Science, 238:347–362, 2000.

10. D. Sieling. New lower bounds and hierarchy results for restricted branching programs. Journal of Computer and System Sciences, 53:79–87, 1996.

11. J. Simon and M. Szegedy. A new lower bound theorem for read-only-once branching programs and its applications. In Advances in Computational Complexity Theory, vol. 13 of DIMACS Series in Discrete Mathematics and Theoretical Computer Science, pp. 183–193. AMS, 1993.

12. I. Wegener. On the complexity of branching programs and decision trees for clique functions. Journal of the ACM, 35:461–471, 1988.

13. I. Wegener. Branching Programs and Binary Decision Diagrams - Theory and Applications. Siam, first edition, 2000.

14. S. Žák. An exponential lower bound for one-time-only branching programs. In Mathematical Foundations of Computer Science: 11th International Symposium, vol. 176 of Lecture Notes in Computer Science, pp. 562–566. 1984.