Wegener I. Complexity Theory. Exploring the Limits of Efficient Algorithms

Подождите немного. Документ загружается.

16.4 The Size of Depth-Bounded Circuits 261

Theorem 16.4.1. The parity function PAR

can be computed by an alter-

nating circuit of depth (log n)/log log n +1 and size O(n

/log n).

Proof. We begin with an EXOR-circuit for which the gates have a fan-in

of log n. In order to represent PAR

, it is suﬃcient to build a balanced

formula tree with O(n/log n) gates and depth (log n)/ log log n.Nowwe

replace the EXOR-gates with both disjunctive and conjunctive forms. These

each have size 2

log n−1

+1≤ n + 1. This increases the size of the circuit to

O(n

/log n) and the depth to 2 ·(log n)/log log n levels that we imagine as

(log n)/log log n layers of depth 2. The negations are again pushed to the

inputs. The inputs of the gates G in the ﬁrst level of a layer are gates from the

second level of the preceding layer. Because we used both a DF form and a

CF form, these functions are available at both an AND-gate and an OR-gate.

We choose the gate of the same type as G, which means we can combine the

second level of one layer with the ﬁrst level of the next. In this way the depth

is reduced to (log n)/log log n + 1 without increasing the number of gates.



The following lower bound for PAR

goes back to H˚astad (1989). The

statement that PAR

/∈ AC

had already been proved in some earlier papers

with ever increasing lower bounds, but it was H˚astad’s Switching Lemma that

revealed the core of such lower bounds.

Theorem 16.4.2. Alternating circuits of depth k for PAR

with n ≥ 2 require

at least 2

n

1/k

/10

gates. PAR /∈ AC

. Achieving polynomial size requires at

least depth (log n)/(c + log log n) for some constant c.

Proof. The important part here is the lower bound. From this PAR /∈

and the statement regarding the depth of polynomial-size circuits follow by

simple calculation.

We will prove the lower bound by induction on the depth k of the circuit.

The trick in the inductive proof consists in looking more carefully at the

functions computed at the gates in the second level of the circuit. Either all of

these functions are represented as a DF or all as a CF. By symmetry, it suﬃces

to consider only the ﬁrst case. If we replace each DF with an equivalent CF,

then the gates at levels 2 and 3 are all AND-gates and the two levels can be

combined. Then we can apply the inductive hypothesis to the resulting circuit

of depth k − 1.

Of course, the argument is not quite that simple. For the DF x

+ ···+ x

n−1

, for example, every CF contains at least 2

n/2

clauses,

each of which has a length of at least n/2. H˚astad applied the probabilistic

method (see, for example, Alon and Spencer (1992)) to a random assignment

of randomly selected variables. The number of variables that are ﬁxed by this

assignment should be chosen so that there are enough variables remaining and

so that with positive probability all of the DFs can be replaced by suﬃciently

small CFs. An analysis of this procedure shows that it doesn’t produce the

262 16 The Complexity of Boolean Functions

desired result. So a new parameter s is introduced which measures the largest

number of inputs to a gate in the ﬁrst level. If s is small, as it is for a DF

for x

+ x

+ ···+ x

n−1

, then there is hope that long clauses can be

replaced with the constant 1 with suﬃciently high probability. These ideas

are formalized in H˚astad’s Switching Lemma.

Lemma 16.4.3 (H˚astad’s Switching Lemma). Let f be a DF over n vari-

ables with monomials of length at most s.Letm>0 and let g be a random

subfunction generated by the following random experiment. First n − m vari-

ables are selected uniformly at random and then these variables are set to 0

or 1 independently with probability 1/2. The probability that there is no CF

for g with clauses of length at most t is smaller than (5ms/n)

. 

The technically challenging proof of the Switching Lemma will not be

described here (see Razborov (1995)). We will use the Switching Lemma to

prove the following claim:

• Let S := 2

n

1/k

/10

, n

1/k

/10≥1, n(i):=n/(10 log S)

k−i+1

,andi ∈

{2,...,k+1}. Then there is no alternating circuit for PAR

n(i)

that has

depth i,atmostS gates on the levels 2,...,i, and at most log S inputs

for each gate on level 1.

First we will show how the Theorem follows from this claim. If there were an

alternating circuit for PAR

with depth k and S gates, then we could replace

this circuit with a circuit of depth k + 1 by computing x

,...,x

, x

level 1 with gates that each have one input. This circuit computes the function

PAR

in depth k+1, has at most S gates on the levels 2,...,k+1, and fan-in 1

at each gate at level 1 – a contradiction to the claim for i = k +1.

The proof of the claim follows by induction on i.Fori =2,thenumberof

variables is n(2) and

n(2) = n/(10 log S)

k−1



= (10n log S)/(10 log S)



≥ 10 log S>log S.

In order to compute PAR

n(2)

in depth 2, we would need gates at level 1 with

n(2) > log S inputs since all prime implicants and all prime clauses have this

length. So the claim holds for i =2.

For the inductive step we apply the Switching Lemma or its dual for CFs

with m(i):=n(i)/(10 log S), s := log S,andt := log S. The probability

that a DF or CF cannot be transformed in the desired way into a CF or DF

is smaller than

(5m(i)s/n(i))

≤ (1/2)

log S

=1/S .

So the probability that at least one of the at most S DFs or CFs cannot

be transformed in this way is smaller than 1. This implies that there is an

assignment of n(i) − m(i)ofthen(i) variables such that all DFs or CFs at

16.4 The Size of Depth-Bounded Circuits 263

the second level can be transformed in such a way that the second and third

levels can be merged without increasing the number of gates but reducing the

number of levels by 1. This results in an alternating circuit of depth i − 1

that computes either the parity function or its negation on m(i)=n(i − 1)

variables. For the equality m(i)=n(i − 1) we are using the fact that for

integers a, b,andj the equation a/b

 = a/b

j−1

/b holds. The number of

the gates at levels 2,...,i− 1 remains bounded by S, and the gates at level 1

have at most log S inputs. This contradiction to the inductive hypothesis

completes the proof of the theorem. 

If we now allow EXOR-gates with arbitrarily many inputs, then we can

compute more functions with polynomial size since parity only requires one

gate. We can then replace OR-gates with AND- and NOT-gates, and since

x = x ⊕ 1, NOT-gates can be replaced by EXOR-gates. If we have r parallel

edges as inputs to an EXOR-gate, these can be replaced with r mod 2 edges.

In this way we obtain an alternating circuit with AND- and EXOR-levels.

If we think of EXOR as a Z

-sum, then we can extend this idea to Z

sums. A MOD

-gate outputs the value 1 if and only if the number of 1’s

among the inputs is an integer multiple of m. EXOR-gates are not the same

as MOD

-gates, but we can get a MOD

from an EXOR-gate by adding a

constant 1 input. For MOD

-gates, r inputs that realize the same function

can be replaced by r mod m edges, so again it makes sense to measure the

size of such circuits by counting the number of gates. A MOD

-gate counts

modulo m, so the class of all families f =(f

) of Boolean functions that can

be computed by alternating circuits with constant depth and polynomial size

with AND- and MOD

-gates is denoted ACC

[m] (alternating counting class).

First we consider the case m = 2, which amounts to computation in the

ﬁeld Z

. This suggests the application of algebraic methods. Boolean functions

can be interpreted as Z

-polynomials, and therefore have a degree, namely

the degree of this polynomial. It is simple to compute functions with high

degree. For example, we can compute the polynomial x

···x

, which has

maximal degree n, with a single AND-gate. But this polynomial is similar

to a polynomial of very low degree, namely the constant 0 with degree 0 –

similar in the sense that these polynomials only diﬀer on one input. We can

measure the distance between two functions f and g by counting the number

of inputs a such that f(a) = g(a). Razborov (1987) used this idea to show

that certain explicitly deﬁned functions cannot belong to

ACC

[2]. He showed

that

ACC

[2] functions must be a small distance from a polynomial of low

degree. To show that a function f =(f

)isnotinACC

[2], it suﬃces to show

that the distance between f and any polynomial of low degree is large. Of

course this idea must be quantiﬁed and parameterized by the depth of the

circuit. Razborov investigated the majority function – MAJ = (MAJ

)which

has the value 1 if and only if the input contains at least as many 1’s as 0’s –

and proved the following result.

264 16 The Complexity of Boolean Functions

Theorem 16.4.4. The majority function can be computed by alternating cir-

cuits using AND- and MOD

-gates in O((log n)/log log n) depth and poly-

nomial size, but any such circuit with depth o((log n)/log log n) must have

superpolynomial size. In particular, MAJ /∈

ACC

[2]. 

Smolensky (1987) investigated the

ACC

[m]-classes more generally and proved

the following result.

Theorem 16.4.5. Let p and q be distinct prime numbers and let k be a con-

stant with k ≥ 1. Then MOD

∈ ACC

Only primes and power of primes allow an algebraic approach. For numbers

like m = 6 that are the product of at least two distinct primes, it has not

yet been possible to prove that explicitly deﬁned functions cannot belong to

ACC

[m].

16.5 The Size of Depth-Bounded Threshold Circuits

Since PAR /∈ AC

, in Section 16.4 we allowed EXOR-gates and more gen-

eral MOD

-gates. Analogously, the result that MAJ /∈ ACC

[2] leads to the

idea of allowing MAJ-gates. In order to capture negation, disjunction, and

conjunction in a single type of gate and to make the availability of constant

inputs unnecessary, we will allow all threshold functions T

≥k

and all negated

threshold functions T

≤k

as gates. Recall that these gates check whether there

are at least (or at most) k ones among the inputs to the gate. The resulting

circuits are called threshold circuits and form an adequate model for discrete

neural nets without feedback.

In threshold circuits it can make sense to have parallel edges. The carry

bit (CAR) from the addition of two n bit numbers, for example, can be com-

puted by a threshold gate with exponentially many edges. This is because

CAR

(a, b) takes on the value 1 if and only if the following inequality is sat-

isﬁed:



0≤i≤n−1



0≤i≤n−1

≥ 2

So we can choose the threshold value 2

and use 2

edges from each of a

and

to the threshold gate. So we obtain two complexity measures for the size of

threshold circuits, namely

• the number of edges (wires) and

• the number of gates.

If we are only interested in the number of gates, then we can imagine that

the edges carry integer weights and that threshold gates check whether the

weighted sum of the inputs reaches the threshold value. Since it has only been

possible to prove exponential lower bounds for the size of threshold circuits

with very small constant depth, we will use

0,d

to represent the class of the

16.5 The Size of Depth-Bounded Threshold Circuits 265

families f =(f

) of Boolean functions that can be computed by threshold

circuits with polynomially many unweighted edges in depth d. Surprisingly,

the use of weighted edges only allows us to save at most one level (Goldmann

and Karpinski (1993)).

The goal of this section is to show that IP /∈

0,2

(Hajnal, Maass, Pudl´ak,

Szegedy, and Tur´an (1987)). This is the current limit of our ability to prove

exponential lower bounds. It has not yet been possible to show that there are

any explicitly deﬁned functions that are not in

0,3

. In order to get a feel

for the model, we will begin with two positive results.

Theorem 16.5.1. PAR ∈

0,2

and IP ∈ TC

0,3

Proof. The circuit for PAR

uses only 2 ·n/2 + 1 gates. For the input

x =(x

,...,x

)weputT

≥k

(x)andT

≤k

(x) at the ﬁrst level for each odd

k ≤ n.Ifx contains an even number of 1’s, then every pair (T

≥k

(x),T

≤k

(x))

contains exactly one 1, and so we obtain a 1 at exactly n/2 of the gates

on level 1. If x has an odd number m of 1’s, then the pair (T

≥m

(x),T

≤m

(x))

produces two 1’s, but all other pairs produce one 1 as before. In this case

n/2 + 1 of the gates on level 1 produce a 1. So we can compute parity

with a threshold gate on level 2 that has every gate on level 1 as input and a

threshold value of n/2 +1.

Since IP

(x) is the parity function applied to (x

,...,x

), the preced-

ing result implies that IP ∈

0,3

.Thevaluesx

,...,x

can be computed

on level 1 using T

≥2

) for 1 ≤ i ≤ n, and the parity function on these

outputs can be computed using two additional levels. 

We will show that IP /∈

0,2

by demonstrating that for any partition-

ing of the input bits of a function f =(f

) with small threshold circuits of

depth 2 between Alice and Bob, there is a shorter randomized communica-

tion protocol with public coins and two-sided error than there can be for IP

(see Theorem 15.4.9). In order to work out this connection to communica-

tion complexity, we consider slightly modiﬁed threshold circuits. Instead of

negated threshold gates, we will allow a weight of −1 to be assigned to the

edges. Since the constant 1 is also available to us, and since T

≤k

=1− T

≥k+1

we can then replace negated threshold gates without increasing the number

of edges by more than a factor of 2. For the output gate we want to transform

a threshold value of k into a threshold value of 0 and at the same time ensure

that the weighted sum of the inputs never has the value 0. To do this, we ﬁrst

double all in-coming edges and the threshold value from k to 2k. Since the

weighted sum will then always be even, the threshold value 2k is equivalent to

the threshold value 2k−1. Now if we add 2k−1 inputs to the output gate each

coming from the constant 1 with weight −1, and replace the threshold value

with 0, we obtain a circuit with the same output value as before. Further-

more, the weighted sum of the inputs is always odd, and so never 0. Finally,

we increase the number of inputs to the output gate to the next power of 2

by adding suﬃciently many connections to the constant 0. Together this only

266 16 The Complexity of Boolean Functions

increases the size of the circuit by a constant factor. In the following lemma

we will call such circuits modiﬁed threshold circuits.

Lemma 16.5.2. If f : {0, 1}

→{0, 1} can be computed by a modiﬁed thresh-

old circuit of depth 2 in which every gate has at most M =2

inputs, then

pub

−

(f) ≤ m +2

for every partition of the inputs between Alice and Bob.

Proof. Alice and Bob use the given modiﬁed threshold circuit as the basis of

their communication protocol. With their random bits they select a random

input to the output gate. If we denote the inputs to this gate as f

,...,f

then f(a) = 1 if and only if w

(a)+··· + w

(a) ≥ 0 for the edge

weights w

∈{−1, 1}. Alice and Bob want to compute the value f

(a)for

the randomly selected function f

to determine a “tendency” for the weighted

sum. The function f

is a threshold function over at most M inputs and the

inputs are variables. The weighted sum of the inputs takes on one of the M +1

consecutive values −j,...,0,...,M − j where j is the number of negatively

weighted inputs. Alice computes the portion of this sum that she can evaluate

because she knows the input bits involved. She then sends this value to Bob

using m+1 bits. Now Bob can evaluate the threshold gate and send the result

to Alice, after which they come to the following decision:

• If f

(a) = 0, they use an additional (public) random bit and select the

result at random, since a value of 0 does not indicate any tendency.

• If f

(a) = 1, then their decision is 1 if w

=1,and0ifw

= −1. Here they

are using the tendency indicated by w

(a).

This protocol has length m + 2. Now we estimate the error-probability for

the input a.Letk be the number of functions f

with f

(a)=1andw

=1,

let l be the number of functions f

with f

(a)=1andw

= −1, and let

M − k − l be the number of functions f

with f

(a) = 0. If f(a) = 1, then the

weighted sum of all w

(a) is positive and so k ≥ l + 1. The probability of a

false decision is given by



l +

(M − k − l)



(l − k) ≤

−

For f (a)=0,l ≥ k + 1 and the result follows analogously. 

Theorem 16.5.3. For any constant α<1/4 and a suﬃciently large n,

threshold circuits of depth 2 for IP

require at least 2

αn

edges. In particu-

lar, IP /∈

0,2

Proof. If 2

αn

edges suﬃce to compute the inner product with threshold cir-

cuits of depth 2, then for some constant c,2

αn+c

edges suﬃce for modiﬁed

threshold circuits, and by Lemma 16.5.2

16.6 The Size of Branching Programs 267

pub

2,1/2−1/2

αn+c+1

(IP

) ≤ αn + c +2,

where Alice knows all the a-bits and Bob knows all the b-bits. By Theo-

rem 15.4.9, for this partition of the input

pub

2,1/2−1/2

αn+c+1

(IP

) ≥ n/2 − αn − c − 1 .

For α<1/4 and suﬃciently large n, these bounds contradict each other,

proving the theorem. 

Among the current challenges in the area of circuit complexity are the

following problems:

• Show that explicitly deﬁned Boolean functions cannot be computed

by circuits with linear size and logarithmic depth.

• Show that the formula size for explicitly deﬁned Boolean functions

grows faster than n

/log n.

• Show that explicitly deﬁned Boolean functions do not belong to

ACC

[6].

• Show that explicitly deﬁned Boolean functions do not belong to

0,3

16.6 The Size of Branching Programs

Branching programs were motivated and deﬁned in Section 14.4. The largest

known lower bound for the branching program size of explicitly deﬁned

Boolean functions is based on the same ideas as the largest bound for for-

mula size (see Section 16.3). As in Theorem 16.3.2, for f : {0, 1}

→{0, 1},

let X = {x

,...,x

} represent the set of input variables, let S

,...,S

disjoint subsets of X,andlets

be the number of diﬀerent subfunctions of f

on S

that can be obtained by replacing all variables in X − S

with constants.

Theorem 16.6.1. For disjoint sets S

,...,S

of variables on which f de-

pends essentially,

BP(f)=Ω





1≤i≤k,s

≥3

(log s

)/log log s



Proof. Let G be a branching program of minimal size for f and let t

be the

number of internal vertices of G that are marked with variables from S

.It

suﬃces to prove that for s

≥ 3

= Ω((log s

)/log log s

) .

Since f depends essentially on all variables in S

, t

≥|S

|. On the other

hand, each of the s

subfunctions of f on S

can be realized by a branching

program of size t

+2 since if we replace all variables X−S

with constants, then

268 16 The Complexity of Boolean Functions

the edges entering the vertices marked with these variables can be replaced

with edges to the appropriate successor.

So we are interested in estimating the number of diﬀerent functions that

can be realized by a branching program with t

internal vertices on |S

| vari-

ables. For the internal vertices there are |S

diﬀerent combinations of vari-

able assignments. For the jth vertex there are for each out-going edge t

+2−j

possible successor vertices. So the number we are interested in is at most

((t

+1)!)

. This number is not allowed to be smaller than s

.Fromthe

inequality |S

|≤t

we obtain

≤ t

((t

+1)!)

= t

O(t

)

From this it follows that t

= Ω((log s

)/log log s

)fors

≥ 3. 

Theorem 16.6.2. BP(

ISA

)=Ω(n

/log

n).

Proof. We can make use of the analysis of

ISA

from the proof of The-

orem 16.3.3. We obtain Ω(n/log n) S

-sets, for which log s

= Ω(n)and

therefore (log s

)/log log s

= Ω(n/log n). The bound now follows from Theo-

rem 16.6.1. 

While there are not many methods for proving large lower bounds for

the size of general branching programs for explicitly deﬁned functions, the

situation is better for length-bounded branching programs. We will investigate

how a small branching program G for f leads to a communication protocol for

f and a partition (a, b) of the variables between Alice and Bob. Alice and Bob

agree on a numbering of the vertices in G and divide up the vertices between

them. Variables for which Alice knows the value are called A-vertices, and

the other internal vertices are B-vertices. By symmetry we can assume that

the evaluation of f begins at an A-vertex. Alice follows the computation for

the current input until she comes to a B-vertex or a sink. She then sends

the number of this vertex to Bob. If this vertex was a sink, then both parties

know f(a, b) and have accomplished their task. Otherwise, Bob continues the

computation until reaching an A-vertex or a sink, at which point he sends

the number of this vertex to Alice. Alice and Bob continue in this fashion

until the number of a sink is communicated. With respect to the partition

of the input between Alice and Bob, we deﬁne the layer depth ld(G)asthe

maximal number of messages in the protocol just described. Analogously we

could have broken the computation into A-sections and B-sections and deﬁned

ld(G) as the maximal number of such sections along a computation path.

These considerations lead to the following result about the communication

complexity C(f), where |G| denotes the number of vertices in G.

Lemma 16.6.3. C(f) ≤ ld(G) ·log |G|. 

16.6 The Size of Branching Programs 269

From this lemma we obtain the following inequality:

|G|≥2

C(f)/ ld(G)−1

In Chapter 15 we encountered functions f

deﬁned on n variables with

C(f

)=Θ(n). In the case of general branching programs, however, we can-

not rule out the possibility that ld(G)=Ω(n). The lower bound then becomes

useless. For this reason we consider the following restricted variant of branch-

ing programs.

Deﬁnition 16.6.4. Let X = {x

,...,x

} be the variable set under consid-

eration. For s ∈ X

,ans-oblivious branching program consists of m +1

levels such that for 1 ≤ i ≤ m each vertex in level i is labeled with s

, level

m +1 contains sinks, and all edges run from level i to some level j with j>i.

For a k-indexed BDD (k-IBDD), s is a concatenation of k permutations of

X. For a k-ordered BDD (k-OBDD), s is a concatenation of k copies of one

permutation of X.

With oblivious branching programs we can hope that the variables can be

divided between Alice and Bob in such a way that the layer depth remains

small. The restricted branching programs that we just introduced, especially

the 1-OBDDs (which we will abbreviate OBDDs) have practical importance

as a data structure for Boolean functions. OBDDs with a ﬁxed permutation of

variables (also called a variable ordering) are the most common data structure

for Boolean functions and support many operations on Boolean functions (see,

for example, Wegener (2000)). This data structure is of limited practical value,

however, if the functions being considered do not have small representations.

This motivates the study of lower bounds for the size of these branching

programs and selected functions. We will restrict our attention to the mask

variant EQ

∗

of the equality test and to the computation of the middle bit

of multiplication MUL

. Recall that the communication complexity of EQ

∗

is at least m if Alice knows m of the a-variables and Bob knows m of the

b-variables, or vice versa. The communication complexity of MUL

is at least

m/8,ifAliceandBobeachknowm variables of one of the factors.

For the investigation of k-OBDDs, we give Alice an initial segment of the

variables (with respect to the variable ordering), and give the rest to Bob.

This bounds the layer depth by 2k.ForEQ

∗

the initial segment ends when

for the ﬁrst time n/2 a-variables or n/2 b-variables are in the segment.

For MUL

, we divide up the variables in such a way that Alice receives n/2

and Bob n/2 of the variables of the ﬁrst factor. This leads to the following

lower bounds.

Theorem 16.6.5. The size of k-OBDDs that compute EQ

∗

or MUL

Ω(n/k)

. 

For k-IBDDs and s-oblivious branching programs we can only guarantee

a small layer depth for small variable sets A, B ⊆ X. This leads to good

270 16 The Complexity of Boolean Functions

lower bounds for the representation size of f if there is an assignment for the

variables outside of A ∪ B such that the communication complexity of the

resulting subfunction for the variable partition (A, B) is large. The functions

∗

and MUL

have this property.

For k-IBDDs, we start with two disjoint variable sets A and B, i.e., a

partition of the variables between Alice and Bob. We consider the ﬁrst variable

ordering as a list and put a dividing line after we have seen for the ﬁrst time

either |A|/2 A-variables or |B|/2 B-variables at the beginning of the list.

In the ﬁrst case |A|/2 A-variables before the dividing line and the at least

|B|/2 B-variables after the dividing line survive. The other case is analogous,

and in either case only the surviving variables are considered from this point.

This procedure always results in at least |A|/2

 surviving A-variables and

|B|/2

 surviving B-variables. With respect to these variables the layer depth

is at most 2k. It can even happen that the layer depth is less, since A-orB-

layers can be next to each other. For EQ

∗

we start by selecting the set of all

a-variables for A and the set of all b-variables for B. For MUL

we can divide

up the variables of the ﬁrst factor uniformly between A and B.

Theorem 16.6.6. Thesizeofk-IBDDs that represent EQ

∗

or MUL

is at

least 2

Ω(n/(k·2

))

. 

Theorem 16.6.6 only leads to superpolynomial lower bounds for k =

o((log n)/log log n). In the general case of k-oblivious branching programs,

let m =4kn for EQ

∗

and let m =2kn for MUL

.Theneachvariableoc-

curs in s on average k times. Note that the variables can occur with diﬀerent

frequencies and do not necessarily occur exactly once in certain blocks. This

situation requires subtler combinatoric methods to show that there are not

small sets A and B for which the layer depth is small. For the functions

∗

and MUL

one can show a lower bound of 2

Ω(n/(k

·2

))

for the size of

s-oblivious branching programs with m =4kn (EQ

∗

)orm =2kn (MUL

The lower bound methods discussed here can also be applied to nonde-

terministic branching programs. Nondeterministic branching programs are al-

lowed to have arbitrarily many 0- and 1-edges at each internal vertex. For

each input a there are then w(a) computation paths that lead to sinks. The

output for OR-nondeterminism is 1 if and only if at least one of these paths

ends at a 1-sink; for AND-nondeterminism all of the paths must end at a

1-sink, and for EXOR-nondeterminism there must be an even number of such

paths. Lemma 16.6.3 can be generalized to all three kinds of nondetermin-

ism. In the communication protocol, Alice and Bob can nondeterministically

select a portion of the computation path within the appropriate layer. This

results in the same lower bounds for MUL

for all three types of nondetermin-

ism. For EQ

∗

the result generalizes only for OR- and EXOR-nondeterminism.

Lower bounds on nondeterministic communication complexity were given in

Theorem 15.3.5.

Lower bounds for general, length-bounded, but not necessarily oblivious

branching programs can only be proven with methods from outside the theory