On the Complexity of Integer Multiplication in Branching Programs with Multiple Tests and in Read-Once Branching Programs with Limited

Nondeterminism

(Extended Abstract)

Philipp Woelfel^{∗} FB Informatik, LS2 Univ. Dortmund

44221 Dortmund, Germany

woelfel@Ls2.cs.uni-dortmund.de

Abstract

Branching Programs (BPs) are a well-established computation and representation model for Boolean functions. Although exponential lower bounds for restricted BPs such as Read-Once Branching Programs (BP1s) have been known for a long time, the proof of lower bounds for important selected functions is sometimes difficult. Especially the complexity of fundamental functions such as integer multiplication in different BP models is interesting.

In [4], the first strongly exponential lower bound of (2^{n/4}) has been proven for the complexity of integer multiplication in the deterministic BP1 model. Here, we consider two well-studied BP models which generalize BP1s by allowing a limited amount of nondeterminism and multiple variable tests, respectively. More precisely, we prove a lower bound of (2^{n/▷7k◁}) for the complexity of integer multiplication in the ▷∨, k◁-BP model. As a corollary, we obtain that integer multiplication cannot be represented in polynomial size by nondeterministic BP1s, if the number of nondeterministic nodes is bounded by logn − loglogn − ω▷1◁. Furthermore, we show that any ▷1, Ck◁-BP representing integer multiplication has a size of (2^{\frac{n}{48▷kC1◁}}). This is not polynomial for k D o▷n/ logn◁.

1. Introduction

1.1 Branching Programs

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 known to be a measure for the space complexity of the corresponding model of sequential computation. Therefore, one is interested in large lower bounds for the complexity of explicitly defined functions in BP models.

Definition 1 A (deterministic) Branching Program (BP) on the variable set Z_{n} D {z_{1}, …, z_{n}} is a directed acyclic graph with one source and two sinks. The internal nodes are marked with variables in Z_{n} and the sinks are labeled with the Boolean constants 0 and 1. Further, each internal node has two outgoing edges, marked with 0 and 1, respectively. A nondeterministic Branching Program is a BP with some additional unmarked nodes having out-degree 2, which are called nondeterministic nodes.

Let G be a (possibly nondeterministic) BP on Z_{n} and a D ▷a_{1}, …, a_{n}◁ ∈ {0, 1}^{n} an assignment to the variables in Z_{n}. A source-to-sink path in G is called computation path of a, if it leaves any node marked with z_{i} over the edge labeled with a_{i}. Note that in a deterministic BP each input defines exactly one computation path, while in a nondeterministic BP multiple computation paths are possible for each input.

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

The size of G, denoted by |G|, is the number of its nodes. The Branching Program complexity of a Boolean function f is the size of the smallest BP representing f.

Until today, no super-polynomial lower bounds for the size of 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.

∗Supported in part by DFG grant We 1066

There are several possibilities to restrict BPs, among them restrictions on the multiplicity of variable tests or the ordering in which variables may be tested.

Definition 2 (i) A Read-Once Branching Program (short: BP1) is a BP where each variable appears on each computation path at most once.

(ii) A BP is called oblivious, if the nodes can be partitioned into levels such that edges point only from lower to higher levels and all internal nodes of one level are marked with the same variable. An Ordered Binary Decision Diagram (short: OBDD) is an oblivious BP1.

(iii) A ▷∨, k◁-BP1 G is a family of k deterministic BP1s G_{1}, …, G_{k}. If f_{1}, …, f_{k} are the functions represented by G_{1}, …, G_{k}, then G represents the function f_{1} ∨ … ∨ f_{k} . The size of G is |G_{1}| C … C |G_{k}|.

OBDDs are probably the most popular Branching Programs, because they have found many applications, e.g. in the area of circuit verification and model checking. On the other hand, BP1s have been studied for a long time by complexity theorists. The first exponential lower bounds date back to the 80s [13, 16], and today, lower bounds for explicitly defined functions are as large as 2^{n−O▷log^{2} n◁} [1]. Borodin, Razborov and Smolensky [5] have presented a lower bound technique for nondeterministic BP1s, and until today, almost all exponential lower bounds for this model are based on their technique.

Note that ▷∨, k◁-BP1s can be regarded as nondeterministic BP1s with k − 1 nondeterministic nodes which are located at the top of the BP1. Lower bounds for this BPmodel have been proven e.g. by Savický and Sieling [11]. It is motivated by Jain, Bitner, Fussell and Abraham [8], who suggested to use so-called Partitioned BDDs, which are ▷∨, k◁-BP1s where the corresponding BP1s are in fact OBDDs.

In order to consider more general BP models than BP1s, one can allow to test variables more than once on the computation paths. Then, one can either restrict the number of tests for each variable or the number of variables which are allowed to be tested more than once.

Definition 3 (i) A read-k-times Branching Program (short: BPk) is a BP where each variable appears on each computation path at most k times.

(ii) A ▷1, Ck◁-BP is a BP where for each computation path p there exist at most k variables appearing on p more than once.

The technique of Borodin, Razborov and Smolensky [5] also allows exponential lower bounds for syntactic BPks, i.e. BPks, where the restriction that each variable can be tested at most k times holds even for each graph-theoretical path. Super-polynomial lower bound proofs for ▷1, Ck◁- BPs can be found in several papers, and have been proven for values of k up to o▷n/ logn◁ [9].

1.2. Integer Multiplication

In order to prove exponential lower bounds for arbitrary but explicitly defined Boolean functions, the functions are often ”designed” in such a way that they fit the lower bound techniques. But besides the interest in finding lower bounds as large as possible or proving lower superpolynomial lower bounds for more and more general BP models, it is necessary to determine the complexity of important Boolean functions. Furthermore, it is generally a more difficult task to prove large lower bounds for some predefined and interesting function. Finding lower bound proofs for such functions may either help to develop new or refined proof-techniques, or can lead to new insights in the properties of the considered function.

Motivated by the applications the basic arithmetic functions are of particular interest.

Definition 4 The function MUL_{k,n} : {0, 1}^{n} × {0, 1}^{n} → {0, 1}is the Boolean function which computes the bit z_{k} of the product ▷z_{2n−1} …z_{0}◁ of two n-bit integers ▷x_{n−1} …x_{0}◁ and ▷y_{n−1} …y_{0}◁.

Generally, the middle bit of integer multiplication (i.e. the ▷n − 1◁th) bit is the most difficult bit to compute. Hence, we consider the function MUL :D MUL_{n−1,n} .

Bryant [6] has proven an exponential lower bound of 2^{n/8} for the function MUL in the OBDD model, and Gergov has shown an exponential lower bound for nondeterministic linear-length oblivious Branching Programs [7]. Ponzio later showed that the complexity of this function is 2^{▷\sqrt{n}◁} for BP1s [10]. Recently, progress in determining the complexity of integer multiplication was obtained by a new approach in the analysis of MUL, which was based on universal hashing. Woelfel [14] improved Bryant’s lower bound in the OBDD model to (2^{n/2}) and Bollig and Woelfel [4] showed a lower bound of (2^{n/4}) for general BP1s.

But oblivious BPs are very restricted in the sense that the variable tests have to be performed in the same order on every computation path. A generalization of obliviousness for nondeterministic BP1s is obtained by restricting the order of variable tests in such a way that it equals for each input the order of variable tests being performed in a complete deterministic BP1 (the so-called graph ordering). The resulting restricted nondeterministic BP1s are called graphdriven and if the graph ordering is a tree, then they are called tree-driven. An exponential lower bound for nondeterministic tree-driven BP1s representing MUL was proven by Bollig [2]. Using the results about integer multiplication from [4], Bollig, Waack, and Woelfel [3] have proven an exponential lower bound for the complexity of MUL in restricted parity-nondeterministic graph-driven BP1s (paritynondeterminism means that the function value equals 1 iff an odd number of computation paths for the given input reaches the 1-sink).

1.3. Results

Nevertheless, there is yet no super-polynomial lower bound known for MUL in the general nondeterministic BP1 model or for deterministic BPks with k > 1. Furthermore, all the known lower bounds require that the BP model is either read-once and deterministic or that the order in which variable tests can be performed is somehow restricted.

One contribution of this paper consists of exponential lower bounds for nondeterministic BP1s which obey no restriction on the ordering of variable tests, but where the amount of nondeterminism is limited. More precisely, we prove that any ▷∨, k◁-BP1 for MULhas a size of (2^{n/▷7k◁}). As a corollary, we obtain that any nondeterministic BP1 for MUL has super-polynomial size if the number of nondeterministic nodes is bounded by logn − loglogn − ω▷1◁. Furthermore, we present the first exponential lower bound for a deterministic nonoblivious model allowing multiple variable tests. We show that any ▷1, Ck◁-BP for MUL has a size of (2^{\frac{n}{48▷kC1◁}}) and hence is not polynomial if k D o▷n/ logn◁. This matches asymptotically the best known values of k, for which super-polynomial lower bounds have been proven [9].

In order to prove the results, we define properties of Boolean functions, and prove that these properties imply the desired lower bounds. This way, we obtain new lower bound techniques for the two models, which might be of independent interest.

2. Preliminaries

In the following text, we consider functions defined on the n C m Boolean variables X_{n} D {x_{1}, …, x_{n}}and Y_{m} D {y_{1}, …, y_{m}}. We denote by B_{nCm} the set of Boolean functions f : {0, 1}^{n} × {0, 1}^{m} → {0, 1}, and assume that an input to such a function is always specified by an assignment to the variables in X_{n}∪Y_{m}. If not otherwise specified, then X_{n} is the set of all n-bit strings and Y_{m} is the set of all m-bit strings and the elements of X_{n} and Y_{m} are specified by assignments to the variables in X_{n} and Y_{m}, respectively. Hence, a function f ∈ B_{nCm} takes as input a pair ▷a, b◁ ∈ X_{n} × Y_{m}.

If we do not want to distinguish between x- and yvariables, then we talk about z-variables, where we mean variables in Z_{nCm} D {z_{1}, …, z_{nCm}}. A partial assignment to Z_{nCm} is an element α D ▷α_{1}, …, α_{nCm}◁ ∈ {0, 1, ∗}^{nCm}. While a position α_{i} with value 0 or 1 means that the input variable z_{i} is fixed to the corresponding constant, a value of ∗ means that the input variable remains free. The set S▷α◁ :D {z_{i} | α_{i} D̸ ∗}is called the support of α. We say that a complete assignment a D ▷a_{1}, …, a_{nCm}◁ to Z_{nCm} is consistent with a partial assignment α to the z-variables, if a_{i} D α_{i} for all z_{i} ∈ S▷α◁. If f ∈ B_{nCm} and α is a partial assignment to Z_{nCm}, then f |_{α} is the subfunction of f obtained by restricting it to inputs consistent with α. If α and β are partial assignments with disjoint supports, then αβ means the partial assignment for which

▷αβ◁_{i} D \{ \begin{matrix}α_{i} & if z_{i} ∈ S▷α◁ \\ β_{i} & if z_{i} ∈ S▷β◁ \\ ∗ & otherwise. \end{matrix}

If α and β are partial assignments with the same support, then D▷α, β◁ denotes the set of variables z_{i} ∈ S▷α◁ (D S▷β◁), for which α_{i} D̸ β_{i}. Finally, let p be a path in a BP G leading from the source to an arbitrary node. We say that a partial input α induces the path p, if α_{i} D c (c ∈ {0, 1}) for any c-edge of p leaving a node marked with z_{i}.

3. Lower Bounds for ▷∨, k◁-BP1s

In [15], a property called k-wise l-mixed has been defined for Boolean functions. It was proven there, that any function having this property has a complexity of 2^{▷l◁} in the ▷1, C▷k − 1◁◁-BP model and in the nondeterministic BP1 model, where the number of nondeterministic nodes is bounded by k − 1. The reason why we cannot simply apply this technique to the function MUL is that it is not possible to distinguish between different variable types by using the technique. More precisely, the technique requires to consider different subfunctions which are obtained by setting arbitrary variables to constants. Hence, for integer multiplication, two different subfunctions might be obtained by assigning different constants to some x- and some y-variables. But the properties we know about integer multiplication allow us only to consider partial assignments, where either only the x-assignments or only the y-assignments differ. Therefore, we introduce a somewhat related but more involved property of Boolean functions, which can cope with two types of variables, and is applicable to integer multiplication.

3.1. The Lower Bound Technique

We define this property by the description of a k-round game played by two players, Alice and Bob. We call the game G^{∨} ▷f, k, l, ε◁, where f ∈ B_{nCm}, k is the number of rounds, l is a positive integer, and 0 ≤ ε ≤ 1.

Let B_{0} D Y_{m}. Alice starts the ith round (1 ≤ i ≤ k ) by choosing a subset A_{i} ⊆ B_{i−1} , |A_{i}| ≥ ε|B_{i−1} |, a set V_{i} ⊆ X_{n} \ ▷V_{1} ∪ … ∪ V_{i−1} ◁, |V_{i}| ≤ l, and two partial assignments α_{i} D̸ β_{i} with support V_{i}. After that, Bob finishes the round by choosing B_{i} ⊆ A_{i} and γ_{i} ∈ {α_{i}, β_{i} }.

We denote by γ_{i}^{∗} the element in {α_{i}, β_{i} } \ {γ_{i}} (for 1 ≤ i ≤ k ), and after a k-round game we let c D γ_{1} …γ_{k} and c_{i} be the partial input obtained from c by replacing γ_{i} with γ_{i}^{∗}. Bob wins the game, if after k rounds there exists an element b ∈ B_{k} and a partial assignment a to the variables in X_{n} \ ▷V_{1} ∪ … ∪ V_{k}◁ such that

f |_{c}▷a, b◁ D 1 ∧ ( ⋁_{jD1}^{k} f |_{c_{j}} ▷a, b◁ D 0) .

Otherwise, Alice wins.

If Bob has a winning strategy for the game G^{∨} ▷f, k, l, ε◁ for some function f ∈ B_{nCm}, then the function has a property which makes it hard for ▷∨, k◁-BP1s.

Theorem 1 Let f ∈ B_{nCm} and k and l be two integers with 1 ≤ kl < n. If Bob has a winning strategy for the game G^{∨} ▷f, k, l, ε◁, where ε ≥ 1/2^{2l−1} , then any ▷∨, k◁- BP1 representing f has a size of at least 2^{l−1} C 2.

The theorem will be proven in the rest of this section. In order to do so, we state after the following definition a lemma which implies that if a ▷∨, k◁-BP1 {G_{1}, …, G_{k}}is too small, then Alice can make her choices in such a way that each computation path induced by c and c_{j} (1 ≤ j ≤ k) will meet at an edge in G_{j} .

Definition 5 Let e D ▷u, v◁ be an edge of a deterministic BP G defined on some variable set Z. The set L_{G}▷e◁ consists of all pairs ▷τ, τ′◁ of partial assignments to the variables in Z for which the following two conditions are fulfilled.

1. S▷τ◁ D S▷τ′◁ and τ D̸ τ′.

2. The partial assignments τ and τ′ induce computation paths p and p′starting at the source and passing through e such that any variable in D▷τ, τ′◁ is either tested on p and p′before v is reached or is not tested on any path from v to a sink.

We denote by L_{G} the union of all L_{G}▷e◁.

The idea behind the set L_{G}▷e◁ is that a computation reaching an edge e cannot distinguish two partial inputs τ, τ′with ▷τ, τ′◁ ∈ L_{G}▷e◁. In other words, the BP ”forgets” at the edge e that τ and τ′are different.

Lemma 1 Let G be a deterministic BP1 representing a function f ∈ B_{nCm} depending on the n C m variables in X_{n} ∪ Y_{m}, and let Y^{∗} ⊆ Y_{m}. Let further 1 ≤ l < n be an integer such that |G| ≤ 2^{l−1} C 1. Then there exist

1. an edge e in G,

2. a set V ⊆ X_{n}, |V |D l,

3. partial assignments α D̸ β to the x-variables with S▷α◁ D S▷β◁ D V,

4. and a set Y′⊆ Y^{∗} with |Y′| ≥ |Y^{∗}|/2^{2l−1}

such that (▷α, b◁, ▷β, b◁) ∈ L_{G}▷e◁ for all b ∈ Y′.

This lemma is the main ingredient to the lower bound proof of Theorem 1. In order to prove it, we combine the idea behind the well-known lower bound technique for BP1s of Simon and Szegedy [12] with the following combinatorial statement, which helps us to cope with two different variable types.

Proposition 1 Let D D ▷d_{i,j} ◁ be an ▷r × c◁-matrix over {0, 1}having at least a fraction of ε (0 ≤ ε ≤ 1) 1-entries. Then there exist two rows i D̸ i′ such that for at least εc▷ε − 1/r◁ columns j the entries d_{i,j} and d_{i′,j} are equal to 1.

Proof. We define for a column j and for two different rows i, i′

δ_{j} ▷i, i′◁ :D \{ \begin{matrix}1 & if d_{i,j} D d_{i′,j} D 1, and \\ 0 & otherwise. \end{matrix}

Let further γ_{j} be the total number of 1-entries in column j. Since ∑ _{jD1}^{c} γ_{j} ≥ εrc by the assumption that at least an ε-fraction of the matrix entries equals 1, we have

∑_{jD1}^{c} \binom{γ_{j}}{2} D ∑_{jD1}^{c} \frac{γ_{j} ▷γ_{j} − 1◁}{2}

≥ ∑_{jD1}^{c} \frac{1}{2} \frac{εrc}{c}( \frac{εrc}{c} − 1 ) D \frac{εrc▷εr − 1◁}{2}. (1)

For the inequality we have used the convexity of \binom{x}{2}. Therefore, we get

∑_{{1≤i<i′≤r \atop 1≤j≤c}} δ_{j} ▷i, i′◁ D ∑_{jD1}^{c} ∑_{1≤i<i′≤r} δ_{j} ▷i, i′◁

D ∑_{jD1}^{c} \binom{γ_{j}}{2} ≥^{(1)} \frac{εrc▷εr − 1◁}{2}.

Hence, by the pigeon hole principle there exist two rows i < i′such that

∑_{jD1}^{c} δ_{j} ▷i, i′◁ ≥ ∑_{{1≤i<i′≤r \atop 1≤j≤c}} \frac{δ_{j} ▷i, i′◁}{\binom{r}{2}}

≥ \frac{εrc▷εr − 1◁/2}{r▷r − 1◁/2} ≥ εc▷ε − 1/r◁,

which proves the claim.

We are now ready to prove Lemma 1.

Proof of Lemma 1. For each node u of G except the root we let u^{C} be the set of variables x_{i} ∈ X_{n} for which there exists a path from u to a sink passing over a node marked with x_{i}. Similarly, we let u^{−} be the set of variables x_{i} ∈ X_{n} for which there exists a path from the source to u passing over a node marked with x_{i}. (Note that if u is marked with x_{i} then u^{C} ∩ u^{−} D {x_{i}}). For the root r we let r^{C} D X_{n} and r^{−} D {x_{j}}if r is marked with x_{j} and r^{−} D ∅ if r is marked with a y-variable.

We define a cut C through the BP1, which is the set of edges e D ▷u, v◁ for which |u^{C}| > n − l and for which |v^{C}| ≤ n−l. Since r^{C} D X_{n} for the root r, s^{C} D ∅ for each sink s, and v^{C} ⊆ u^{C} for each edge ▷u, v◁, it follows that each graph-theoretical source-to-sink path passes through exactly one edge in the cut C.

For each such edge e D ▷u, v◁ ∈ C, we let V_{e} ⊆ X_{n} be an arbitrary l-element set for which u^{−} ⊆ V_{e} ⊆ X_{n} \ v^{C}. (Such a set exists for each edge in C, because |u^{−} | ≤ l, |X_{n} \ v^{C}| ≥ l and u^{−} ⊆ X_{n} \ v^{C}.) Hence, all x-variables being tested on any path from the source to e are contained in V_{e}, but no variable in V_{e} is tested on a path from e to a sink. Clearly, for any fixed b ∈ Y^{∗} the elements a ∈ X for which the inputs ▷a, b◁ pass over e are uniquely defined by their setting of the variables in V_{e}.

Following standard graph theoretical arguments it can be seen that C contains at most |G|−1 edges. Therefore, by the pigeon-hole principle, there exists an edge e ∈ C such that at least 2^{l}|Y^{∗}|/▷|G| − 1◁ different elements ▷α, b◁, where α is a partial assignment with support V_{e} and b is an element of Y^{∗}, induce computation paths passing over e. Now assume that ▷α, b◁ and ▷β, b◁ are two different such elements. It is obvious that then (▷α, b◁, ▷β, b◁) ∈ L_{G}▷e◁.

We choose V D V_{e} (recall that |V_{e}| D l). We have to show that there exist two different assignments α, β to the variables in V as well as a set Y′ ⊆ Y^{∗} of large enough size such that all partial inputs ▷α, b◁ and ▷β, b◁ for b ∈ Y′ induce computation paths passing over e. In order to do so, we consider a ▷2^{l} × |Y^{∗}|◁-matrix D, where each row is associated with a partial assignment to the x-variables having support V and where each column is associated with an element b ∈ Y^{∗}. We write d_{α,b} for the entry in the row associated with the partial x-assignment α and in the column associated with b. We let each entry d_{α,b} be 1 if the partial input ▷α, b◁ passes over e and 0 otherwise.

By the discussion above, we know that the fraction of 1-entries in the matrix is at least 1/▷|G| − 1◁ ≥ 1/2^{l−1} . Applying Proposition 1 we obtain that there exist two different rows associated with α and β, respectively such that the number of elements b ∈ Y^{∗} with d_{α,b} D d_{β,b} D 1 is bounded below by

1/2^{l−1} · |Y^{∗}|(1/2^{l−1} − 1/2^{l} ) ≥ |Y^{∗}|/2^{2l−1} .

Let these α and β be fixed and let Y′ be the set of the |Y^{∗}|/2^{2l−1} corresponding complete y-assignments. Then for each b ∈ Y′we have (▷α, b◁, ▷β, b◁) ∈ L_{G}▷e◁.

The following obvious fact helps us to apply Lemma 1

Fact 1 Let G be a deterministic BP representing the function f, ▷τ, τ′◁ ∈ L_{G} and z be an assignment to the variables not in S▷τ◁. Then either f |_{τ}▷z◁ D f |_{τ′}▷z◁ or there exists a variable in D▷τ, τ′◁ which is tested more than once on the computation path of τz (and on the computation path of τ′z).

We can finally prove the correctness of the lower bound technique.

Proof of Theorem 1. Let G_{1}, …, G_{k} be deterministic BP1s such that G D {G_{1}, …, G_{k}} is an ▷∨, k◁-BP1 with at most 2^{l−1} C 1 nodes representing a function f. We show the theorem by describing a winning strategy for Alice.

She will make her choices in such a way that after the ith round

∀b ∈ B_{i} :  (2)
(▷γ_{1} …γ_{i}, b◁, ▷γ_{1} …γ_{i−1} γ_{i}^{∗}, b◁) ∈ L_{G_{i}}.

In the first round Alice achieves this by applying Lemma 1 to G_{1} for Y^{∗} D B_{0} (D Y_{m}). This is possible because |G_{1}| ≤ |G| ≤ 2^{l−1} C 1 as required by the lemma. Let α_{1} and β_{1} be assignments obtained this way and A_{1} ⊆ B_{0} be the resulting set of y-inputs. Note that |A_{1}| ≥ ε|B_{0}| for our choice of ε. Alice chooses V_{1} D S▷α_{1}◁ (D S▷β_{1}◁). Then we have |V_{1}| D l, α_{1} D̸ β_{1}, and after Bob’s choice of γ_{1} ∈ {α_{1}, β_{1} } and B_{1} ⊆ A_{1}, (2) is fulfilled.

Assume now that (2) holds after the ith round (1 ≤ i < k ). In the ▷i C 1◁th round we consider the BP1 G_{▷iC1◁}|_{γ_{1}...γ_{i}}, which is obtained from G_{i} by restricting it to inputs according to γ_{1} …γ_{i}. Such a restriction is easily obtained by replacing any node with its d-successor, if it is marked with a variable x_{j}, which is set by γ_{1} …γ_{i} to the Boolean constant d. We apply now Lemma 1 in the same way as in the first round, but now to the restricted BP1 G^{∗} :D G_{▷iC1◁}|_{γ_{1}...γ_{i}} and for Y^{∗} D B_{i}. (Note that G^{∗} is defined on at least n − il > l x-variables.) Then there exists an edge e, the set A_{iC1} ⊆ B_{i} and the partial assignments α_{iC1} and β_{iC1} such that (▷α_{iC1}, b◁, ▷β_{iC1}, b◁) ∈ L_{G^{∗}}▷e◁. Again it holds that |A_{iC1}| ≥ ε|B_{i}|. As in the first round, Alice chooses V_{iC1} D S▷α_{iC1}◁ (D S▷β_{iC1}◁) and because V_{iC1} D l and α_{iC1} D̸ β_{iC1}, the choice is made according to the rules of the game. Obviously, any input passing through the edge e in G^{∗} also passes through the same edge in G. Hence, (▷γ_{1} …γ_{i}α_{iC1}, b◁, ▷γ_{1} …γ_{i}β_{iC1}, b◁) ∈ L_{G} for all b ∈ A_{iC1}. Altogether, after Bob’s choice of γ_{iC1} ∈ {α_{iC1}, β_{iC1} }(2) holds again.

Now assume that Alice and Bob have played the game k rounds such that (2) was fulfilled after each round. Let a be an arbitrary assignment to the variables in X_{n}\▷V_{1}∪…∪V_{k}◁ and let b ∈ B_{k}. We show that Alice has won the game, i.e.

f |_{c}▷a, b◁ D 0 ∨ ( ⋁_{jD1}^{k} f |_{c_{j}} ▷a, b◁ D 1) ,  (3)

where c and c_{j} are defined as in the description of the game. We assume that f |_{c}▷a, b◁ D 1 because otherwise there is nothing to show. In this case, there exists a deterministic BP1 G_{i} ∈ {G_{1}, …, G_{k}} computing 1 for the input ▷γ_{1} …γ_{k}a, b◁. Note that b ∈ B_{k} and hence by the rules of the game b ∈ B_{i}, too. Since (2) was fulfilled after each round, we know that (▷γ_{1} …γ_{i}, b◁, ▷γ_{1} …γ_{i−1} γ_{i}^{∗}, b◁) ∈ L_{G}. Then, because G_{i} is read-once, Fact 1 implies that f |_{γ_{1}...γ_{i},b}▷a◁ D f |_{γ_{1}...γ_{i−1} γ_{i}^{∗},b}▷a◁ and therefore

f ▷γ_{1} …γ_{k}a, b◁ D f ▷γ_{1} …γ_{i−1} γ_{i}^{∗}γ_{iC1} …γ_{k}a, b◁.

Hence, f |_{c_{i}}▷a, b◁ D f |_{c}▷a, b◁ D 1, which proves (3).

3.2. A Lower Bound for Integer Multiplication

In this section, we derive the lower bound for MUL in the ▷∨, k◁-BP model.

Theorem 2 Any ▷∨, k◁-BP1 for MUL has a size of (2^{n/▷7k◁}).

Note that we can ”simulate” any nondeterministic BP1 G with t nondeterministic nodes by a ▷∨, k◁-BP1, k D 2^{t}, which has a size of at most k|G|. This is done by hardwiring each of the at most 2^{t} possible nondeterministic decision-strings into G, which yields k deterministic BP1s. Hence, we obtain the following corollary from Theorem 2.

Corollary 1 Any nondeterministic BP1 for MUL which contains at most t nondeterministic nodes has a size of 2^{▷n/2^{t}◁−t} , which is not polynomial for t D logn − loglogn − ω▷1◁ .

We prove Theorem 2 for the subfunction MUL′ :D MUL|_{y_{0}D1} of MUL, where the y-inputs are restricted to odd integers.

Let 1 ≤ l ≤ ▷n − 6◁/▷7k◁ − 3/7 and ε D 1/2^{2l−1} . We show in the rest of the section that Bob has a winning strategy for the game G^{∨} ▷MUL′, k, l, ε◁. Then Theorem 2 follows right away from Theorem 1 and from the fact that MUL′is a subfunction of MUL.

Let ℤ_{2^{n}} be the set of n-bit integers and ℤ_{2^{n}}^{∗} D {1, 3, …, 2^{n} − 1 }be the set of odd n-bit integers. For the ease of notation, we do not distinguish between n-bit strings and the corresponding integer values if we consider inputs for the function MUL′. E.g., we write MUL′▷x, y◁ as well for ▷x, y◁ ∈ ℤ_{2^{n}} × ℤ_{2^{n}}^{∗} as for ▷x, y◁ ∈ {0, 1}^{n} × {0, 1}^{n−1} . Note also, that the set of x-variables specifying the x-input for MUL′is now {x_{0}, …, x_{n−1} }D: X′_{n}. If τ is a partial assignment to the variables in X′_{n}, then |τ|denotes the integer in ℤ_{2^{n}} which corresponds to the bit string t_{n−1} …t_{0}, where t_{i} D τ_{i} if x_{i} ∈ S▷τ◁ and t_{i} D 0 otherwise.

Fact 2 If τ, τ′ are partial assignments to the x-variables such that S▷τ◁ ∩ S▷τ′◁ D ∅, then |τ|C |τ′| D |ττ′|.

We first recall two results about integer multiplication, which have been obtained mainly in [4] but were stated in this form explicitly in [3].

Lemma 2 ([3, 4]) Let Y ⊆ ℤ_{2^{n}}^{∗}, 1 ≤ r ≤ n − 2 and ▷z_{i}, z′_{i}◁ ∈ ℤ_{2^{n}} × ℤ_{2^{n}}, 1 ≤ i ≤ s, where z_{i} D̸ z′_{i}. Then there exists a subset Y′ ⊆ Y, |Y′| ≥ |Y |− s · 2^{n−rC2} such that

∀y ∈ Y′, 1 ≤ i ≤ s :

4 · 2^{n−r} ≤ (▷z_{i} − z′_{i}◁y) mod 2^{n} ≤ 2^{n} − 4 · 2^{n−r} .

Lemma 3 ([4]) Let X ⊆ ℤ_{2^{n}} and Y ⊆ ℤ_{2^{n}}^{∗}. If |X| · |Y |≥ 2^{nC2rC1} for some integer r ≥ 0, then there exists an element y ∈ Y such that for all q ∈ {0, …, 2^{r} − 1 }

∃x ∈ X : q2^{n−r} ≤ ▷xy◁ mod 2^{n} < ▷q C 1◁2^{n−r} .

The following proposition is obtained in an easy but somewhat technically way from the previous lemma. We state it in such a way that we can use it for the proof of Theorem 2 as well as for the lower bound proof for ▷1, Ck◁- BPs in the next section. The proof is omitted due to space restrictions.

Proposition 2 Let X ⊆ ℤ_{2^{n}}, y ∈ ℤ_{2^{n}}^{∗}, z, z_{1}, …, z_{k} ∈ ℤ_{2^{n}}, and r ∈ ℕ such that the following two properties are fulfilled.

1. ∀q ∈ {0, …, 2^{r} − 1 }∃x ∈ X :

q2^{n−r} ≤ ▷xy◁ mod 2^{n} < ▷q C 1◁2^{n−r} .

2. ∃C ∈ {−1, C1 }: ∀1 ≤ i ≤ k:

2^{n−1} ≤ (C▷z_{i} − z◁y) mod 2^{n} ≤ 2^{n} − 4 · 2^{n−r} .

Then there exists x ∈ X such that for all 1 ≤ i ≤ k MUL▷x C z, y◁ > MUL▷x C z_{i}, y◁.

Let in the following r D k▷2l C 1◁ C 2 and recall that l ≤ ▷n − 6◁/▷7k◁ − 3/7. It is easy to derive the following inequality.

n C 2r C 1 ≤ 2n − kl − k▷2l C 1◁ − 1.  (4)

We are now ready to describe Bob’s strategy. Consider a partial assignment γ_{1} …γ_{i−1} obtained after the ▷i − 1◁th round as well as two assignments α_{i} and β_{i} to some xvariables in V_{i}. Further, let A_{i} ⊆ B_{i−1} be chosen by Alice. Bob will make his choices in such a way that the following invariants are fulfilled after the ith round.

(i) |B_{i}| ≥ 2^{n−1−i▷2lC1◁} .

(ii) ∀b ∈ B_{i} : 2^{n−1} ≤ (b|γ_{i}^{∗}| − b|γ_{i}|) mod 2^{n} ≤ 2^{n} − 4 · 2^{n−r} .

Obviously, the proof of the following two claims completes the proof of Theorem 2.

Claim 1 Bob can achieve (i) and (ii) after the ith round for i D 1, …, k.

Claim 2 If (i) and (ii) hold after the ith round for i D 1, …, k, then Bob wins the game.

Proof of Claim 1. For i D 0, we have |B_{0}| D |ℤ_{2^{n}}^{∗}| D 2^{n−1} . Hence (i) is fulfilled when the game starts or after the 0th round. We show now that if (i) holds after the ▷i − 1◁th round, then Bob can make his choices in such a way that (i) and (ii) also hold after the ith round.

Let α_{i} D̸ β_{i} and A_{i} be the choices of Alice in this round. By the rules of the game, |A_{i}| ≥ ε|B_{i−1} | D 2^{−▷2l−1◁} |B_{i−1} |, and hence because (i) was fulfilled in the previous round

|A_{i}| ≥ 2^{n−1−▷i−1◁▷2lC1◁−▷2l−1◁} D 2^{n−i▷2lC1◁C1}. (5)

Because α_{i} and β_{i} are different, obviously |α_{i}| D̸ |β_{i}|. We apply Lemma 2 in order to obtain a set Y′ ⊆ A_{i}, |Y′| ≥ |A_{i}| − 2^{n−rC2} , such that

∀b ∈ Y′: 4 · 2^{n−r} ≤ ▷b|α_{i}| − b|β_{i}|◁mod 2^{n} ≤ 2^{n} − 4 · 2^{n−r} .

Note that if (b|α_{i}| − b|β_{i}|) mod 2^{n} ≤ 2^{n−1} , then (b|β_{i}| − b|α_{i}|) mod 2^{n} ≥ 2^{n−1} and vice versa. Hence, Bob may choose γ_{i} ∈ {α_{i}, β_{i} }such that for at least half of the elements b ∈ Y′it holds (b|γ_{i}^{∗}| − b|γ_{i}|) mod 2^{n} ≥ 2^{n−1} . Bob then chooses B_{i} to be exactly the set of these elements in Y′, so that we obtain altogether

∀b ∈ B_{i} : 2^{n−1} ≤ (b|γ_{i}^{∗}| − b|γ_{i}|) mod 2^{n} ≤ 2^{n} − 4 · 2^{n−r} , and (ii) holds. Furthermore, we have

|B_{i}| ≥ |Y′|/2 ≥ \frac{|A_{i}| − 2^{n−rC2}}{2} .

Note that because i ≤ k, we obtain from (5) that |A_{i}|/2 ≥ 2^{n−k▷2lC1◁} D 2^{n−rC2} (recall that r D k▷2l C 1◁ C 2). Hence,

|B_{i}| ≥ \frac{|A_{i}| − |A_{i}|/2}{2} D |A_{i}|/4 ≥^{(5)} 2^{n−1−i▷2lC1◁} .

Therefore, also (i) is fulfilled.

Proof of Claim 2. Let the game have been played k rounds such that (i) and (ii) hold after each round. We let z D |γ_{1} …γ_{k}| and z_{j} D |γ_{1} …γ_{j−1} γ_{j}^{∗}γ_{jC1} …γ_{k}|.

We have to show how to choose an element b ∈ B_{k} and a partial assignment a to the variables in X′_{n}\ ▷V_{1} ∪ … ∪ V_{k}◁ such that for all 1 ≤ j ≤ k

MUL′▷|γ_{1} …γ_{k}a|, b◁ >
MUL′▷|γ_{1} …γ_{j−1} γ_{j}^{∗}γ_{jC1} …γ_{k}a|, b◁.

Because of Fact 2, we can write this inequality as

MUL′▷z C |a|, b◁ > MUL′▷z_{j} C |a|, b◁.  (6)

Let X′be the set of all integers |a|, where a is an assignment to the variables in X′_{n} \ ▷V_{1} ∪ … ∪ V_{k}◁. Obviously, |X′| ≥ 2^{n−kl}. Furthermore, it is |B_{k}| ≥ 2^{n−1−k▷2lC1◁} , because invariant (i) is fulfilled after the kth round. Hence, we get

|X′| · |B_{k}| ≥ 2^{2n−kl−k▷2lC1◁−1} ≥^{(4)} 2^{nC2rC1}.

Applying Lemma 3, we can choose an element b ∈ B_{k} such that

∀q ∈ {0, …, 2^{r} − 1 }∃x ∈ X′:

q2^{n−r} ≤ ▷xb◁ mod 2^{n} < ▷q C 1◁2^{n−r} . (7)

Let this b be fixed from now on. Recall that z D |γ_{1} …γ_{k}| and z_{j} D |γ_{1} …γ_{j−1} γ_{j}^{∗}γ_{jC1} …γ_{k}|. Hence, by Fact 2

z_{j} − z D |γ_{j}^{∗}| − |γ_{j} |, and thus because of (ii) and because b ∈ B_{k} ⊆ B_{j}

∀1 ≤ j ≤ k :

2^{n−1} ≤ ▷z_{j} b − zb◁ mod 2^{n} ≤ 2^{n} − 4 · 2^{n−r} . (8)

By (7) and (8) all preconditions of Proposition 2 are fulfilled, and therefore there exists an element x ∈ X′such that for all 1 ≤ j ≤ k

MUL▷z C x, b◁ > MUL▷z_{j} C x, b◁.

Since b is odd, the same result holds also for MUL′and thus (6) is proven for all 1 ≤ j ≤ k.

4. Lower Bounds for ▷1, Ck◁-BPs

Similarly as in Section 3 we define now a property of Boolean functions, which allows us to prove exponential lower bounds in the ▷1, Ck◁-BP model. As in the previous section the main difficulty lies in the task to cope with two different variable types. Moreover, it seems not possible to prove something similar as Lemma 1 for ▷1, Ck◁-BPs. Therefore, the property we describe now differs from the one used in the previous section. We describe it though, again by a game played by two players, Alice and Bob.

Let f ∈ B_{nCm}. The game we describe below is called G^{C}▷f, k, l, t◁, where k and l are positive integers and t ≥ k is the number of rounds (tl ≤ m C n).

Alice starts the ith round ▷1 ≤ i ≤ t◁ by choosing a set V_{i} ⊆ ▷X_{n} ∪ Y_{m}◁ \ ▷V_{1} ∪ … ∪ V_{i−1} ◁such that |V_{i}| ≤ l. Further, Alice chooses two partial assignments α_{i} D̸ β_{i} with support V_{i} which differ only in their settings to variables of one type, i.e. D▷α_{i}, β_{i}◁ ⊆ X_{n} or D▷α_{i}, β_{i}◁ ⊆ Y_{m}. After that, Bob chooses γ_{i} ∈ {α_{i}, β_{i} }. The game is finished after the tth round.

Let c D ▷γ_{1} …γ_{t}◁ and c_{j} be the partial assignment obtained from c by replacing γ_{j} with γ_{j}^{∗}, where as in the previous sections γ_{j}^{∗} is the element in {α_{j} , β_{j} } \ {γ_{j} }. Bob wins the game, if there exist a set I ⊆ {1, …, t} of at least k indices and a partial assignment λ to the variables in ▷X_{n} ∪ Y_{n}◁ \ ▷V_{1} ∪ … ∪ V_{t}◁ such that

∀j ∈ I : f |_{c}▷λ◁ D̸ f |_{c_{j}} ▷λ◁.

Otherwise, Alice wins.

Theorem 3 Let f ∈ B_{nCm}, l ≥ 4, and tl ≤ n C m. If Bob has a winning strategy for the game G^{C}▷f, k, l, t◁, then any ▷1, C▷k − 1◁◁-BP representing f has a size of at least 2^{l/4−2} C 2.

In order to prove the theorem by describing a winning strategy for Alice, we use the following lemma.

Lemma 4 Let f ∈ B_{nCm} and 4 ≤ l ≤ n C m. If G is a deterministic BP representing f with at most 2^{l/4−2} C1 nodes, then there exist two partial assignments α, β with support V such that the following three conditions are fulfilled.

1. |V |≤ l.

2. D▷α, β◁ ⊆ X_{n} ∨ D▷α, β◁ ⊆ Y_{n}.

3. ▷α, β◁ ∈ L_{G}.

Proof. Let l′ D ⌊▷l C 3◁/4⌋ ≥ l/4. We denote by p_{a,b} the computation path of the input ▷a, b◁ ∈ X_{n} × Y_{m}. On each path p_{a,b} we determine the edge e_{a,b} through which the path passes after either exactly l′x-variables or exactly l′y-variables have been tested. If p_{a,b} is a path testing less than l′ x- and less than l′ y-variables, then e_{a,b} is the last edge on the path (i.e. the edge pointing to a sink).

Since G has two sinks with out-degree 0 and |G| − 2 internal nodes with out-degree 2, G contains exactly 2▷|G| − 2◁ edges. Hence, by the pigeon hole principle, there exists an edge e such that for at least

\frac{|X||Y |}{2▷|G| − 2◁} > \frac{2^{nCm}}{2 · 2^{l/4−2}} ≥ 2^{nCm−l/4C1} ≥ 2^{nCm−l′C1}

inputs ▷a, b◁ it holds e_{a,b} D e. Furthermore, there exists one type of variables – w.l.o.g. the y-variables – such that at least half of the inputs ▷a, b◁ with e_{a,b} D e test on their paths to the edge e less than l′ y-variables. Considering only these inputs, we can then find (again by the pigeon hole principle) an element b ∈ Y_{m} and a set X′ ⊆ X_{n}, |X′| > 2^{n−l′}, such that for all a ∈ X′it holds e_{a,b} D e and all paths p_{a,b} test less than l′ y-variables before edge e is reached. Let this b be fixed from now on.

Now assume first that there exists an element a ∈ X′ such that p_{a,b} tests also less than l′x-variables before edge e D e_{a,b} is reached. Then by definition, e points to a sink. Let τ be the partial assignment which defines exactly the path p_{a,b}. (I.e. the ith bit of τ is set to the ith bit of ▷a, b◁ if this bit is tested on the path p_{a,b} and set to ∗ otherwise.) Since less than l′x- and less than l′y-variables are tested on p_{a,b}, we have S▷τ◁ ≤ 2▷l′− 1◁. We choose an arbitrary x-variable x_{i} ∉ S▷τ◁ and let α and β be the partial inputs extending τ by the additional assignment x_{i} D 0 and x_{i} D 1, respectively. Clearly, we then have α D̸ β, S▷α◁ D S▷β◁ and the only variable in D▷α, β◁, namely x_{i}, is tested on no path from e to a sink. Hence, ▷α, β◁ ∈ L_{G}▷e◁. Furthermore, letting V D S▷α◁ we get |V |≤ 2l′−1 ≤ l, and since finally D▷α, β◁ D {x_{i}}⊆ X_{n}, the claim is proven for this case.

We now consider the other case, namely that for all a ∈ X′ the path p_{a,b} tests exactly l′ x-variables before it reaches edge e. Assume that all a ∈ X′differ in no variable being tested on a path p_{a,b} before edge e is reached. Then clearly all paths p_{a,b} are equal before edge e, and hence all a ∈ X′ have the same support S such that |S ∩ X_{n}| D l′. But this is impossible, because there are at most 2^{n−l′} possible assignments to the x-variables not in S, while we have |X′| > 2^{n−l′}.

Hence, there exist two different elements a′, a′′ ∈ X′ such that there is at least one variable x_{i} ∈ D▷a′, a′′◁ being tested on p_{a′,b} and p_{a′′,b} before edge e. Let V′be the set of variables being tested on p_{a′,b} and V′′be the set of variables being tested on p_{a′′,b} before edge e is reached on these paths. Note that V′and V′′may contain different x- and yvariables, but they have at least the variable x_{i} in common. Because by construction |V′|, |V′′ | ≤ 2l′− 1, we obtain for V :D V′∪ V′′that |V | ≤ 4l′− 3. We choose α to be the partial assignment with support V which equals ▷a′, b◁ on the variables in V′and equals ▷a′′, b◁ on the variables in V \ V′. Similarly, we choose β to be the partial assignment with support V which equals ▷a′′, b◁ on the variables in V′′ and equals ▷a′, b◁ on the variables in V \ V′′. This way, α and β are different partial assignments with support V, and have an equal setting to all variables in V \ ▷V′∩ V′′◁ . Hence, D▷α, β◁ ⊆ V′ ∩ V′′. Furthermore, α and β induce the sub-paths of p_{a′,b} and p_{a′′,b}, respectively, which lead from the source to edge e. Since by construction, each variable in D▷α, β◁ ⊆ V′∩ V′′is tested on both paths before edge e is reached, we obtain ▷α, β◁ ∈ L_{G}▷e◁. Furthermore, α and β are defined for the same b, and hence we have D▷α, β◁ ⊆ X_{n}. Together with |V | ≤ 4l′− 3 ≤ l, all three conditions of the claim are fulfilled.

We can now use this lemma in order to prove Theorem 3.

Proof of Theorem 3. Assume that G is a ▷1, C▷k − 1◁◁-BP for the function f and that |G| ≤ 2^{l/4−2} C 1. We describe a winning strategy for Alice.

In the first round, Alice chooses α_{1}, β_{1} with support V_{1} according to Lemma 4. Hence, |V_{1}| ≤ l, and α_{1} and β_{1} differ only in their settings to the x-variables or only in their settings to the y-variables and are therefore chosen in accordance with the rules of the game. Furthermore, ▷α_{1}, β_{1}◁ ∈ L_{G}. After that, Bob chooses γ_{1} ∈ {α_{1}, β_{1} }.

Consider now the ▷i C 1◁th round, i C 1 ≤ t. We let G|_{γ_{1}...γ_{i}} be the ▷1, C▷k − 1◁◁-BP obtained from G by restricting it to the partial assignment γ_{1} …γ_{i}. (See the proof of Theorem 1 for how to do this.) Note that the function f |_{γ_{1}...γ_{i}} represented by G|_{γ_{1}...γ_{i}} still depends on at least l variables. Applying Lemma 4, Alice can find analogously to the first round α_{iC1}, β_{iC1} such that D▷α_{iC1}, β_{iC1}◁ is a subset of X_{n} or of Y_{m} and ▷α_{iC1}, β_{iC1}◁ ∈ L_{G|_{γ_{1}...γ_{i}}}. It is easy to see that then ▷γ_{1} …γ_{i}α_{iC1}, γ_{1} …γ_{i}β_{iC1}◁ ∈ L_{G} and of course D▷γ_{1} …γ_{i}α_{iC1}, γ_{1} …γ_{i}β_{iC1}◁ is also a subset of either X_{n} or Y_{m}.

Altogether, we obtain that Alice can make her choices in such a way that after t rounds the following holds (recall the definition of c and c_{j} at the description of the game).

∀1 ≤ j ≤ t : ▷c, c_{j} ◁ ∈ L_{G}.  (9)

Let then I be a set of k indices in {1, …, t} and λ be an arbitrary assignment to the variables in ▷X_{n} ∪ Y_{m}◁ \ ▷V_{1} ∪ … ∪ V_{t}◁. We consider the computation path p of the input cλ (D γ_{1} …γ_{t}λ). Since at most k − 1 variables can be tested more than once on p, and since the k variable sets V_{i}, i ∈ I, are all disjoint, there is an index j ∈ I such that each variable in V_{j} is tested at most once on p. But clearly D▷c, c_{j} ◁ ⊆ V_{j}, and hence Fact 1 together with (9) tells us that f |_{c}▷λ◁ D f |_{c_{j}} ▷λ◁. Therefore, Alice has won the game.

Using this technique, one may finally obtain an exponential lower bound for MUL in the ▷1, Ck◁-BP model.

Theorem 4 Any deterministic ▷1, Ck◁-BP for MUL has a size of (2^{\frac{n}{48▷kC1◁}}).

Proof of Theorem 4. We prove the theorem for the subfunction MUL′′:D MUL|_{x_{0}D1,y_{0}D1}, which computes the middle bit of the product of two odd n-bit integers. Let k ≥ 1, l D ⌊n/▷12k◁ − 4/3⌋, t D 4k and r D 4k C ⌈logk⌉C 5. We show that Bob has a winning strategy for the game G^{C}▷MUL′′, k, l, t◁. The theorem then follows right away from Theorem 3.

We even show that Bob wins the game independently of his choices. Let all the partial assignments γ_{i}, γ_{i}^{∗} with support V_{i} (1 ≤ i ≤ t) be somehow determined according to the rules of the game, and let c and c_{i} be defined as usual. Since D▷c, c_{i}◁ D D▷γ, γ_{i}◁ is either a subset of X_{n−1} or of Y_{n−1} , there exists a set J of at least t/2 D 2k indices in {1, …, t}such that all sets D▷c, c_{j} ◁, j ∈ J, contain only variables of one and the same type. Hence, assume w.l.o.g. that D▷c, c_{j} ◁ ⊆ X_{n} for all j ∈ J.

We let z ∈ ℤ_{2^{n}}^{∗} be the odd integer obtained by fixing z_{0} D 1 and setting all bits z_{i}, 1 ≤ i < n, according to the setting of the x-variables x_{i} in c (D γ_{1} …γ_{t}) if x_{i} ∈ S▷c◁ and letting z_{i} D 0 if x_{i} ∉ S▷c◁. In an analogous way we obtain the integers z_{j}, j ∈ J, from the partial assignments c_{j}.

Consider now an arbitrary partial assignment λ D ▷λ_{x}, λ_{y}◁ to the variables in ▷X_{n−1} ∪ Y_{n−1} ◁ \ ▷V_{1} ∪ …∪ V_{t}◁. (Here λ_{x} denotes the partial assignment to the x-variables and λ_{y} the partial assignment to the y-variables.) Let x D |λ_{x}|. The x-integer represented by the input cλ then obviously is zCx and the x-integer represented by c_{j} λ, j ∈ J, is z_{j} C x. Similarly, λ_{y} together with the setting of the yvariables defined by c defines a unique integer y ∈ ℤ_{2^{n}}^{∗}. Note that for j ∈ J this integer is the same, if we replace c with c_{j}, because then γ_{j} and γ_{j}^{∗} do not differ in the yvariables. Hence, the integers x and y are uniquely defined by the choice of ▷λ_{x}, λ_{y}◁.

Let X′ be the set of all the integers x and Y^{∗} be the set of all the integers y that can be obtained this way from the partial assignments ▷λ_{x}, λ_{y}◁ with support ▷X_{n−1} ∪ Y_{n−1} ◁ \ ▷V_{1} ∪ … ∪ V_{t}◁. In order to show that Bob has won the game, we have to prove that there exists a partial assignment λ D ▷λ_{x}, λ_{y}◁ with support ▷X_{n−1} ∪ Y_{n−1} ◁ \ ▷V_{1} ∪ … ∪ V_{t}◁ and a set I ⊆ J, |I| ≥ k, such that

∀j ∈ I : MUL′′|_{c}▷λ◁ D̸ MUL′′|_{c_{j}} ▷λ◁.

In our notation, this is equivalent to showing that there exists a pair ▷x, y◁ ∈ X′× Y^{∗} and a set I ⊆ J, |I| ≥ k, such that

|I| ≥ k and  (10)
∀j ∈ I : MUL▷z C x, y◁ D̸ MUL▷z_{j} C x, y◁.

Note that V_{1}∪…∪V_{t} contains at most tl variables. Since λ_{x} and λ_{y} are partial assignments to the x- and y- variables not in V_{1} ∪ … ∪ V_{t}, we have |X′|, |Y^{∗}| ≥ 2^{n−1−tl} and |X′| · |Y^{∗}| ≥ 2^{2n−2−tl} . We consider now the |J | D 2k pairs ▷z, z_{j} ◁, j ∈ J. By Lemma 2, there exists a subset Y′⊆ Y^{∗} such that

∀y ∈ Y′, j ∈ J :  (11)

4 · 2^{n−r} ≤ (▷z_{j} − z◁y) mod 2^{n} ≤ 2^{n} − 4 · 2^{n−r} ,

and |Y′| ≥ |Y^{∗}| − |J | · 2^{n−rC2} . Recalling that r D 4kl C ⌈logk⌉C 5 and t D 4k, we obtain

|J |·2^{n−rC2} D 2k ·2^{n−4kl−⌈logk⌉−3} ≤ 2^{n−tl−2} ≤ |Y^{∗}|/2.

Hence, |Y′| ≥ |Y^{∗}| − |Y^{∗}|/2 ≥ |Y^{∗}|/2. Using l ≤ n/▷12k◁ − 4/3, this yields

|X′| · |Y′| ≥ |X′| · |Y^{∗}|/2 ≥ 2^{2n−tl−3} D 2^{2n−4kl−3}
D 2^{▷5/3◁nC▷16/3◁k−3} ≥ 2^{▷5/3◁nC7/3}.

(For the last inequality we have used k ≥ 1.) Using this inequality, we obtain further

2^{nC2rC1} D 2^{nC8klC2⌈logk⌉C11}
D 2^{▷5/3◁n−▷32/3◁kC2⌈logk⌉C11} ≤ |X′| · |Y′|.

Hence, we may apply Lemma 3, and obtain an element y ∈ Y′such that

∀q ∈ {0, …, 2^{r} − 1 }∃x ∈ X′:

q2^{n−r} ≤ ▷xy◁ mod 2^{n} < ▷q C 1◁2^{n−r} . (12)

Let this y be fixed from now on.

Note that for any z_{j}, j  ∈  J, we
have  either  2^{n−1} ≤ (▷z_{j} − z◁y) mod 2^{n}  or

2^{n−1} ≤ (▷z − z_{j} ◁y) mod 2^{n} . Hence, either for C D −1 or for C D 1 we obtain for at least half of the indices j ∈ J that 2^{n−1} ≤ (C▷z_{j} − z◁y) mod 2^{n}. Let I be the set of these indices, |I| ≥ |J |/2. Invoking (11), we get then altogether

∀j ∈ I :  (13)

2^{n−1} ≤ (C▷z_{j} − z◁y) mod 2^{n} ≤ 2^{n} − 4 · 2^{n−r} .

We may apply now Proposition 2, noting that due to (12) and (13) all preconditions of this proposition are fulfilled for the elements z_{j} ∈ I. Hence, we obtain that there exists x ∈ X such that MUL▷x C z, y◁ > MUL▷x C z_{j} , y◁ for all j ∈ I. Since |I| ≥ |J |/2 ≥ k, this proves (10).

Acknowledgment

I thank Ingo Wegener for helpful comments on this text and Beate Bollig for fruitful discussions on Branching Programs and Integer Multiplication.

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 Proc. of 26th ICALP, volume 1644 of LNCS, pages 179–189, 1999.

[2] B. Bollig. Restricted nondeterministic read-once branching programs and an exponential lower bound for integer multiplication. RAIRO, 35:149–162, 2001.

[3] B. Bollig, S. Waack, and P. Woelfel. Parity graph-driven read-once branching programs and an exponential lower bound for integer multiplication. Technical Report TR01-73, ECCC, 2001.

[4] B. Bollig and P. Woelfel. A read-once branching program lower bound of ▷2^{n/4}◁ for integer multiplication using universal hashing. In Proc. of 33rd ACM STOC, pages 419–424, 2001.

[5] A. Borodin, A. Razborov, and R. Smolensky. On lower bounds for read-k-times branching programs. Comput. Complex., 3:1–18, 1993.

[6] R. E. Bryant. On the complexity of VLSI implementations and graph representations of boolean functions with applications to integer multiplication. IEEE Transactions on Computers, 40(2):205–213, 1991.

[7] J. Gergov. Time-space tradeoffs for integer multiplication on various types of input oblivious sequential machines. Information Processing Letters, 51:265–269, 1994.

[8] J. Jain, J. Bitner, D. S. Fussell, and J. A. Abraham. Functional partitioning for verification and related problems. In Brown MIT VLSI Conference, pages 210–226, 1992.

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

[10] S. Ponzio. A lower bound for integer multiplication with read-once branching programs. Siam Journal on Computing, 28:798–815, 1998.

[11] P. Savický and D. Sieling. A hierarchy result for read-once branching programs with restricted parity nondeterminism. In Proc. of 25th MFCS, volume 1893 of LNCS, pages 650– 659, 2000.

[12] 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, volume 13 of DIMACS Series in Discrete Mathematics and Theoretical Computer Science, pages 183–193. AMS, 1993.

[13] I. Wegener. On the complexity of branching programs and decision trees for clique functions. J. of the ACM, 35(2):461–471, 1988.

[14] P. Woelfel. New bounds on the OBDD-size of integer multiplication via universal hashing. In Proc. of 18th STACS, volume 2010 of LNCS, pages 563–574, 2001.

[15] P. Woelfel. A lower bound technique for restricted branching programs and applications. In Proc. of 19th STACS, volume 2285 of LNCS, pages 431–442, 2002.

[16] S. Žák. An exponential lower bound for one-time-only branching programs. In Proc. of 11th MFCS, volume 176 of LNCS, pages 562–566, 1984.