On relations between counting communication complexity classes.
We develop upper and lower bound arguments for counting acceptance modes of communication protocols. A number of separation results for counting communication complexity classes is established. This extends the investigation of the complexity of communication between two processors in terms of complexity classes initiated by Babai et al. (Proceedings of the 27th IEEE FOCS, 1986, pp. 337-347) and continued in several papers (e.g., J. Comput. System Sci. 41 (1990) 402; 49 (1994) 247; Proceedings of the 36th IEEE FOCS, 1995, pp. 6-15). In particular, it will be shown that for all pairs of distinct primes <i>p</i> and <i>q</i> the communication complexity classes MOD<inf><i>p</i></inf><i>P</i><sup>cc</sup> and MOD<inf><i>q</i></inf><i>P</i><sup>cc</sup> are incomparable with regard to inclusion. The same is true for PP<sup>cc</sup> and MOD<inf><i>m</i></inf><i>P</i><sup>cc</sup>, for any number <i>m</i>2. Moreover, non-determinism and modularity are incomparable to a large extend. On the other hand, if <i>m</i>=<i>p</i><inf>1</inf><i>l</i><inf>1</inf>'...' <i>p</i><inf>r</inf><i>l</i><inf>r</inf> is the prime decomposition of <i>m</i> 2, then the complexity classes MOD<inf><i>m</i></inf><i>P</i><sup>cc</sup> and MOD<inf><i>(m)</i></inf><i>P</i><sup>cc</sup> coincide, where <i>(m)</i>=<i>p</i><inf>1</inf>'...'<i>p</i><inf>r</inf>. The results are obtained by characterizing the modular and probabilistic communication complexity in terms of the minimum rank of matrices ranging over certain equivalence classes. Methods from algebra and analytic geometry are used. This paper is the completely revised and strongly extended version of the conference paper Damm et al. (Proc. 9th Ann. STACS, pp. 281-291) where a subset of the results was presented.
Introduction
Communication complexity plays an important role in theoretical studies: many of the known
lower-bound results are obtained by analyzing the communication between various parts of
the computational device. This concerns area-time tradeoffs for VLSI-computations ([1],
[9]), time-space tradeoffs for Turing machines, width-length tradeoffs for oblivious and usual
branching programs and
hing programs ([2], [12]). Moreover, lower bounds on the
depth of monotone circuits ([16]), structural results in designing pseudorandom sequences
([4]), and lower bounds on the size of special threshold circuits of depth 3 ([8]) should be
mentioned in this connection.
Babai, Frankl, and Simon in [3] introduced the investigation of the complexity of communication
between two processors in terms of complexity classes. They showed some analogies
between Turing machine classes like P , NP , PP , etc. and the corresponding communication
complexity classes P cc , NP cc , PP cc , etc. Halstenberg and Reischuk in [6] and [7] studied
different measures of communication complexity of discrete functions.
In this paper we study counting acceptance modes for nondeterministic communication
protocols introduced in [7]. Certain types of counting communication complexity classes were
also studied in [11]. The arising complexity classes are analogues of Turing machine based
complexity classes. These were extensively studied in the last years and many oracle separations
are known (cf., e.g., [5]). Counting acceptance modes for communication protocols
have also proved to be useful for proving lower bounds for certain types of depth restricted
circuits (see [10], [13], [17]). Further, in [20] it has been shown that all problems computable
by constant depth, polynomial size circuits with modm -gates for arbitrary integers m, i.e.,
ACC-functions, are contained in certain counting communication complexity classes.
This paper is organized as follows. In Section 2 the model is introduced. Section 4 is
focused on finding complete problems for the various counting communication complexity
classes. These are target functions for the separation results. Sections 5 and 6 are the heart
of the paper as to the methods used. We derive rank arguments for proving upper and lower
bounds there.
We use the characterization results of Section 5 to describe the relations between the
complexity classes under consideration:
1. For m - 2 the classes PP cc and MODmP cc are incomparable with regard to inclusion
(Section 7, Theorem 18). This extends the result MOD 2 P cc 6' PP cc proved in [7] with
the ffl-discriminator method.
2. If
r is the prime factorization of m then the mod ae(m) -mode is as powerful
as the modm-mode, where ae Theorem 5.)
3. The computational powers of the acceptance modes mod p and mod q are incomparable
in the case of p 6= q being prime numbers. If, moreover, m is a proper multiple but not
a power of the prime number p, then the mode modm is strictly more powerful than
the mode mod p , i.e., MOD p P cc ae MODmP cc (Section 8, Theorem 24).
4. Nondeterminism and modularity are incomparable to a large extent (Section 9, Theorem
27).
Preliminaries
Let X and Y be disjoint sets. We consider the following two-party communication game on
Two players, which we denote by X and Y, have to compute the value of a function
on an input (x; y), where X has only access to x 2 X and Y has only
access to y 2 Y . The players share a blackboard, where they can exchange bits subject to
a given communication protocol. In the deterministic version of a protocol at each step the
next bit to be communicated is completely determined by the input and the communication
history (the string on the blackboard). Although, when describing protocols we will do this
mostly in an informal way, we need a formal definition.
Recall the following standard notation. Given a directed full binary tree with a distinguished
root, we label the outgoing edges of each inner node by 0 and 1, respectively. Then
each node in the tree will be denoted by the string that describes the path from the root to
this node. In particular, the root of the tree is denoted by the empty string -.
Formally defined a deterministic (two-party) communication protocol P on X \Theta Y is
given by a finite directed rooted tree whose inner nodes are partitioned into X -nodes and
Y -nodes. Let Z be any of X and Y. Each Z -node v is labeled by a mapping
We write b v (x; y) to uniquely denote b v (x) or b v (y) without specifying whether v is type X
or Y. Each node is a state in the communication process. The process starts at the root.
The type of the actual node determines the player to communicate next. The value b v (x; y)
is the bit to be communicated by the player in turn upon seeing his part of the input (x; y)
and the communication history v.
A computation (of length t) of protocol P on input (x; y) 2 X \Theta Y is given by a leaf
of the tree such that for 1
(using the
convention -). The last bit of a computation is called the output of the computation
on (x; y). We call a computation accepting if the output is 1 and rejecting otherwise. Observe
that for each input (x; y) there is exactly one computation of a given deterministic
communication protocol on (x; y). The function f that maps (x; y) to
the output of this single computation of P on (x; y) is called the function computed by P .
We will base our constructions on nondeterministic protocols. In a nondeterministic
protocol the bit to be announced by the player in turn need not be uniquely defined by the
proper part of the input and the communication history. This is accomplished by setting the
range of the mappings b v to ff0g; f1g; f0; 1gg for inner nodes v of the tree. Computations
of the protocol on input (x; y) are leaves of the tree that fulfill w
t.
In the sequel the term "communication protocol" refers to both, deterministic and non-deterministic
protocols.
A nondeterministic protocol may have several accepting or rejecting computations on
the same input. Given a protocol P let acc P (x; y) and rej P (x; y), respectively, denote the
number of different accepting and rejecting, respectively, computations of P on input (x; y).
Using (counting) acceptance modes we will interpret these numbers in various ways to define
the function computed by the protocol.
Any defines an acceptance mode in the following way. We
holds
In particular we will consider the following acceptance modes for nondeterministic protocols:
ffl the nondeterministic mode: - n (ff;
ffl the co-nondeterministic mode: - co-n (ff;
ffl modular modes: -mod m (ff; fixed positive integer
m, and
ffl the probabilistic mode: - prob (ff;
where ff and ae stand for nonnegative integers. Observe that for deterministic protocols
all mentioned acceptance modes (except for the co-nondeterministic one) lead to the same
computed function. To enable unified terminology we may speak of the deterministic mode
although it is understood that determinism is a property of the protocol not of a special
acceptance mode. Further, we will often speak of -protocols, instead of nondeterministic
protocols with acceptance mode -.
The complexity of a communication is its length, i.e., the depth of the leaf in the protocol
tree. The complexity (or length) of a protocol is the maximum complexity of its computa-
tions. The -communication complexity c - (f) of a function f : X \Theta Y ! f0; 1g is the
minimum complexity of a communication protocol on X \Theta Y that -computes f . Especially
we speak of the deterministic, nondeterministic, co-nondeterministic, mod m-, and probabilistic
communication complexity of a function. We will use the notations c d (f ), c n (f ),
c co-n (f ), c mod m (f ), and c prob (f) to denote these.
3 Counting communication complexity classes
Throughout we will consider the case where
Further, without loss of generality we will assume all computations of a given protocol to be
of the same length.
Let L ' \Sigma   be a language containing only strings of even length. A -communication
protocol P for L is a sequence (P n ) of communication protocols, such that for each n protocol
is the characteristic function of L " \Sigma 2n , i.e., L n equals 1 on
vanishes outside this set.
As argued in [3] the natural unit with respect to which to measure communication complexity
is log n (log here and elsewhere denotes logarithm to base 2). Hence a polynomial time
communication protocol is a sequence such that for all n P n is a communication
protocol on \Sigma n \Theta \Sigma n with complexity at most (log n) c , where c is a constant independent of
n. Given a specific acceptance mode - : IN \Theta IN ! f0; 1g we define -P cc as being the class of
all languages for which exist polynomial time nondeterministic -communication protocols.
Classes of this type will be called counting communication complexity classes. Especially we
consider:
g.
The above defined classes are classes of languages, however, they can be seen also as classes of
sequences of 0-1-functions (which we call problems) by identifying a set with its characteristic
function. We will in the sequel freely switch between both concepts.
It will be convenient to consider also the following class introduced in [3]:
g.
1. NP
2. co-NP
3. MODmP
Proof: Obvious from the definitions.
be sequences of functions.
Let k be a nonnegative integer. The sum and product, respectively, of f and g are the
these operations are defined on
individual members of the sequences in the obvious way. Similarly we define the kth binomial
coefficient of f as
ii fn
be a nonnegative integer. #P cc is closed under sum, product, and kth
binomial coefficient, i.e., if f; g belong to #P cc , then f
belong to #P cc as
well.
Proof: Given protocols P and Q on \Sigma n \Theta \Sigma n with acc
and t, respectively. We construct protocols of lengths at most polynomial in s and t whose
number of accepting computations on (x; y) are f n
, respectively. Similar constructions are known for Turing machines (cf. [5]).
For the sum generate a root v   with b v   (x; with the
roots of P and of Q.
For the product connect a the root of a copy of Q to each accepting computation of P .
For the second binomial coefficient consider the "ordered twofold iteration" of P , i.e.,
connect the root of a copy of P to each accepting computation of P and redefine the mappings
b v as follows: For inner nodes v of this tree b v is identical to the corresponding mapping of
the original node in P . Define b w (x; leaves w of the tree, for which
where w 0 and w 00 are accepting computations of P and w 0 is lexicographically smaller than
leaves w of the tree.
For the kth binomial coefficient consider the ordered k-fold iteration of P .
We call the protocols constructed in the proof sum and product of P and Q and kth
binomial coefficient of P , respectively, and denote them by P+Q, P \Delta Q, and
, respectively.
Sum and product easily generalize to any constant number of operands. So we can consider
protocols or sequences of protocols like P k (kth power of P ) or kP (sum of k copies of
Further we will denote by 1 the deterministic protocol that on each input lets player X
announce 1 and stop. Hence protocols p(P can be considered, where are
arbitrary protocols or sequences of protocols and p is a fixed polynomial with nonnegative
integer coefficients.
For a given protocol P we will denote by the protocol which is obtained from P
by switching accepting and rejecting computations.
Lemma 3 Let P be a nondeterministic communication protocol on \Sigma n \Theta \Sigma n and let p be a
prime. Then for each input (x; y) 2 \Sigma n \Theta \Sigma n holds:
1. if P
2. if P
3. if P
proof: The only nontrivial observation is Claim 3, which relies on Fermat's Little Theorem.
In a standard way we will make use of the closure properties mentioned in Lemma 2 and
Lemma 3.
Lemma 4
are positive integers and m 1 divides m 2 , then MODm 1
2. Let m r be pairwise coprime positive integers and
for any language L holds L 2 MODmP cc if and only if there are languages L 1 2
cc such that
3. If p is prime, then MOD p P k.
Sketch of proof: The proof relies on the above lemmas and the following observations:
1. If f 2 #P cc and m 2 =m
2. Let f r be orthogonal idempotents in ZZ=m 1 ZZ \Theta \Delta \Delta \Delta \Theta
ZZ=m r ZZ. Then
Hence for languages L r as in the claim
holds
If, on the other hand, some protocol P computes L modulo m, define L i as the language
that is computed modulo m i by P .
3. For 2: let f 2 #P cc . Based on the identity
l
l! for nonnegative
integers k - l and on divisibility considerations one proves that for (x; y) 2 \Sigma n \Theta \Sigma n
and a = f(x; y) holds
a
a
Routine checking (based on Fermat's Little Theorem) shows that the latter is true if
and only if
a
For general k iterate the construction using
a
a
which is proved from the above by induction.
A consequence of Lemma 4 is:
Theorem 5 Let
r be the prime factorization of the natural number m. Then
4 Complete problems
We consider the following type of reductions introduced in [3]:
Let L 0 ae \Sigma 0  , L 00 ae \Sigma 00  be languages containing only binary strings of even length.
We say that L 0 is rectangular reducible to L 00 , iff there are some constant c and sequences
transformations l
such that for all n and for all
It is not hard to see that for every the complexity class -P cc is closed
under rectangular reductions.
A language L 00 is said to be complete for a communication complexity class C cc , iff
It turns out that all counting communication
complexity classes have complete languages. We describe them as sequences of 0-1-functions.
be an arbitrary counting acceptance mode. The inner product with
respect to - is the problem
Theorem 6 -IP is complete for -P cc with respect to rectangular reductions.
proof: We describe a -protocol of length dlog ne+2 for -IP 2n . It works within 2 rounds.
Round 1: Player X nondeterministically chooses an index l 2 f1; 0g. If x
then the computation stops rejecting. Otherwise X chooses nondeterministically
some index k such that x encoded in binary.
Round 2: If y then the computation stops rejecting. Otherwise player Y announces
the one-bit-message
Clearly, there are
accepting and
rejecting computations on the
input By definition the protocol -computes
the function -IP 2n .
It remains to show that if
reducible to -IP.
Let P be a -protocol of length (without loss of generality we
assume all computations to be of the same length). We fix enumerations c
0; 1-sequences of length t whose last bit is b and define the two transformations l
; for all (x; y) 2 \Sigma 0n \Theta \Sigma 0n by
l
Y are the characteristic functions of valid computations on the input from
X's and Y's viewpoint. More explicit: for w 2 f0; 1g t define - P
there is some
, such that w is a computation of P on input (x; y). Similarly - P
Y is defined. Since
Y only if w is a computation of P on (x; y), the claim follows.
We will consider also the following problems:
ffl inner product mod m:
IP m
(The function
n is the orthogonality test mod m ORT m
studied e.g. in [13].)
ffl Boolean inner product:
(Note that 1 \Gamma BIP n is the set disjointness test SDT n (see e.g. [14]).)
Corollary 7
1. IP m is complete for MODmP cc ,
2. ORT m is complete for MODmP cc , for prime m,
3. BIP is complete for NP cc ,
4. SDT is complete for co-NP cc .
5 Rank arguments for upper and lower bounds
We prove in this section complexity bounds for counting acceptance modes based on ranks
of matrices over semirings in a unifying treatment. Some of the arguments where known
before for specific acceptance modes (see [14]).
Let R be any commutative semiring, i.e., a set R together with two binary operations
and \Delta (addition and multiplication) such that (R; +) and (R; \Delta) are commutative monoids
and multiplication distributes over addition. In a semiring R let 1R denote the multiplicative
unit. Special semirings we consider in this paper are the non-negative integers IN, the Boolean
semiring IB, the integers ZZ, the reals IR, and ZZ=mZZ, the integers modulo m. For any R in
this collection the mapping 1 7! 1R can be extended to a unique semiring homomorphism
from IN to R - the canonic homomorphism.
Given a non-zero m \Theta n matrix M over R let the R-rank of M be the minimum k such
that there exist an m \Theta k matrix A over R and a k \Theta n matrix B over R with
We denote the R-rank of M by rankR (M ). According to this definition a rank 1 matrix is
a matrix M of shape v T \Delta w, where v T is a column vector and w is a row vector. Hence, we
can give a second characterization of matrix ranks:
The following properties of ranks over semirings are easy to prove.
Lemma matrices over R and let h semiring
homomorphism. Then
1. rankR 0 (h(M 1
2. rankR
Throughout we use the following notation: f denotes a function with domain \Sigma n \Theta \Sigma n ,
and M f denotes the corresponding communication matrix, i.e., the j\Sigmaj n \Theta j\Sigmaj n matrix with
entry f(x; y) in row x and column y. This notation is not restricted to 0-1-valued functions.
Rank based lower bound arguments rely on the following lemma.
Lemma 9 Let P be a protocol on \Sigma n \Theta \Sigma n with complexity L. Then
rank IN (M acc P
rank IN (M rej P
proof: Obviously for each (x; y) 2 \Sigma n \Theta \Sigma n holds
acc P (x;
w2f0;1g L ;w L =1
and
rej P (x;
w2f0;1g L ;w L =0
Y are defined as in the proof of Theorem 6. Hence, M acc P
and M rej P
both
are products of matrices of sizes j\Sigmaj n \Theta 2 t\Gamma1 and 2 t\Gamma1 \Theta j\Sigmaj n .
Additionally we will need the notion of variation ranks introduced in [13]:
Let m be a positive integer. Two integer matrices A and B are said to be modm -equivalent
if for all indices i, j,
The modular variation rank var-rank ZZ=mZZ (A) is the minimum of all numbers rank ZZ=mZZ B,
where B is an integer matrix which is modm -equivalent to A.
Two real matrices A and B with non-zero entries are said to be order-equivalent if for
all indices i and j holds
0:
Let ' be a positive natural number and let A be a real matrix with non-zero entries. We
define var-rank -;' (A) to be the minimum over all numbers rank IR (B), where B is a matrix
with entries in f\Sigma1; is order-equivalent to A. We call var-rank -;' (A)
the real variation rank with respect to '.
Now we are prepared to prove bounds for concrete acceptance modes. Except for the
probabilistic acceptance mode the lower bounds are immediate consequences of Lemma 9
together with Lemma 8, Claim 1 applied to the appropriate canonic semiring homomorphism.
Therefore we skip a detailed explanation for these lower bounds.
R be an arbitrary semiring. Then
c d (f) - log
We can fully characterize the modular communication complexity in terms of variation
ranks.
Proposition be a natural number. Then
log
proof: To prove the upper bound, we choose an integer matrix B which is modm -equivalent
to M f , such that
where the B (k) have ZZ=mZZ-rank 1. This is equivalent to B (k)
y mod m, for
U
B. The players execute the following protocol
P of length dlog re
Player X chooses nondeterministically indices k, 1 - k - r, and l 1
x , and
announces (k; l 1 ). Afterwards Y chooses nondeterministically some index l 2
y ,
announces l 2 and accepts.
Clearly, there are
accepting computations assigned
to the input. Hence, f is modm-computed by P .
On the basis of Lemma 3 we can do better in the case of being a prime number.
In this case we denote as usual ZZ=pZZ by IF p .
Proposition 12 Let p be a prime number. Then
log
The upper bounds of the next proposition can be derived as in Proposition 11.
Proposition 13
1. c n
log
2. c co-n
log
rank IB (M 1\Gammaf )
Finally we consider the probabilistic mode.
Lemma 14 Let J be the all-one matrix of size j\Sigmaj n \Theta j\Sigmaj n and let t be the length of a
probabilistic communication protocol computing f . Then
proof: Given a probabilistic protocol P of complexity t for f , we replace it according
to Lemma 3 by a protocol P 0 of complexity at most t that for no input has the same
number of accepting and rejecting computations. M acc P 0
is obviously order-equivalent
to its entries are bounded in absolute value by 2 t+1 . Further the real rank of
the matrix is at most 2 t+1 by Lemma 8 and Lemma 9 .
Lemma 14 differs considerably in structure from the other rank arguments in this section.
Therefore we develop methods to estimate real variation ranks in the next section. The
results might be of independent interest.
6 Estimates for the real variation rank
Throughout this section N is a positive integer. We will consider the real vector space IR N
and, to stress the geometric nature of the arguments, attach a vector symbol to vectors from
this space: ~x.
We recall some notions from linear algebra. Let h~x;
be the standard scalar
product and
h~x; ~xi the induced norm. If is a real N \Theta N-matrix, then
is the spectral norm,
is the l 2 -norm and
a ii is the trace of the matrix A. A regular matrix A is called orthogonal if and
only if A
If ~x and ~y are nonzero vectors, then let
6 (~x; ~y) denote the angle between them. The
cosine of this angle is defined by
If ~x is a vector, and if U ' IR N is a nonzero linear subspace, then
U be the orthogonal projection of IR N onto the embedded subspace. Obvi-
ously, cos(
6 (~x; U)) is always non-negative and
ae cos(
We will use the following well-known facts from linear algebra (see, e.g., [18]):
Fact 1:
A T A
Fact 2: 1
and U is an orthogonal
matrix.
Lemma 15 If H is an N \Theta N-matrix with entries in f\Gamma1; 1g, and is an N \Theta N-matrix
over IR such that A is order-equivalent to H, and 1
then for any \Theta - 1 holds var-rank -;\Theta (H)
proof: Let ~a; ~ b 2 IR N be order-equivalent and 1 - ja \Theta for all
Ng. Then
Analogously h~a; ~ bi - 1
\Theta
Now consider some N \Theta N matrix
such that B is order-equivalent to H (and hence also to A). Let It suffices to
prove
Denote the transposes of the rows of A and B by ~a U be the
subspace spanned by ~ b be an orthonormal basis of U .
We shall estimate the sum
from below and above.
By the properties of the orthogonal projection for all i holds:
By (1) we obtain\Theta'
Consequently, S can be estimated from below as follows:
On the other hand, for
definition of the spectral norm. Thus and we conclude that
or, equivalently,
The claim follows, since
2 by Fact 1.
As an application we prove:
Proposition let A be any real matrix which is order
equivalent to J \Gamma 2M f , such that 1 Further let A 0 be any
square submatrix of A. Then
c prob (f) - log
\Gamma2
log
proof: For the case A A the assertion follows immediately from Lemma 14 and
Lemma 15 by setting
To complete the proof, observe that all arguments so far apply also to a different setting
of communication games, where the players have to compute the function only on a square-
shape subset R \Theta C ' \Sigma n \Theta \Sigma n . Let f and C are the sets of rows
and columns of A 0 . Then we have c prob (f 0
equivalent to J
, where J 0 is the all-one matrix of appropriate size. Since obviously
c prob (f) - c prob (f 0 ), we are done.
By Fact 2 the largest bound is achieved if A 0 is of special shape:
Corollary 17 Let f and A be as in Proposition 16. If A 0 is an N 0 \Theta N 0 -submatrix of A such
that there is some d ? 0 and an orthogonal matrix U such that A
c prob (f) - log N 0 \Gamma2
log
7 Probabilistic versus modular versus nondeterministic
mode
Theorem
be an arbitrary integer. Then PP cc and MODmP cc are incomparable with
regard to inclusion.
2. NP cc and co-NP cc are incomparable with regard to inclusion and properly contained in
PP cc .
In order to prove the theorem we compute the modular as well as the probabilistic
communication complexity of the orthogonality test function introduced in Section 4 and
the sequence equality function SEQ defined by SEQ n
To characterize the modular communication complexity of SEQ ; the following lemma
supplies a necessary and sufficient condition (see Proposition 11).
Lemma 19 Let I N denote the identity N \Theta N-matrix. Let m be a positive integer and let
r be its prime factorization. Then var-rank ZZ=mZZ
proof: First we prove that dN=re is a lower bound. Let A 0 be an N \Theta N matrix with entries
in ZZ=mZZ that is modm -equivalent to I N such that var-rank ZZ=mZZ
By definition of the rank there are integer matrices C and D of sizes N \Theta m and m \Theta N
such that A m. Then the integer matrix -equivalent to
I N and rank ZZ m. By definition we have, for all indices i; j, a ii 6j 0 mod m; and a ij j
there is a k 2 rg such that a ii 6j 0 mod p l k
k .
We conclude that there is a factor p l k
of m such that a ii 6j 0 mod p l k
k for at least dN=re
many i. Let for simplicity p := p k and l := l k . We consider a submatrix B obtained from A
by deleting all rows and columns i for which a ii j 0 mod p l k
k . The remaining set of rows and
columns is denoted by I. For each i 2 I let p l\Gamma- i be the maximal power of p that divides
a ii . Hence
a
a ii 6j 0 mod
for all j 2 I, j 6= i. It is sufficient to show that det B 6= 0 where the determinant is computed
over the reals. Let N It is easy to see that
for all permutations oe of the set different from the identity permutation. Consequently

To prove that dN=re is an upper bound let f
rg. Let A 0 be the unique 0 \Theta 0-matrix, which, of course, has
rank 0. Clearly, A j mod m is a j \Theta j-diagonal matrix of ZZ=mZZ-rank 1, for rg.
Let A be an N \Theta N-matrix consisting of a chain of bN=rc copies of A r (and perhaps an
additional copy of A r 0 , r arranged along the main diagonal and filled with
zeroes outside this chain. It follows that A mod m is a diagonal N \Theta N-matrix, and that
rank ZZ=mZZ
Lemma 19 immediately yields:
Proposition 20 For arbitrary m, we have
c mod m(SEQ n
Let us consider the orthogonality test function ORT p , for p a prime number. First we
need a technical lemma.
Let G n
p be a maximal set of pairwise linear independent vectors. Since there are
vectors in IF n
p and each one has multiples, we have
Lemma
1. #f~z 2 G n
2. #f~z 2 G n
3. #f~z 2 G n
proof: The set fz 2 IF n
(~z; ~y)g is a dimensional linear subspace
of IF n
. The first claim counts a maximal set of pairwise independent non-zero vectors in
this subspace. The second claim follows similarly with the help of the inclusion-exclusion
principle. The third equality follows from the first two.
Proposition 22 Let p be a prime number. Then
c prob (ORT p
. We define the following indexed by G n
p \Theta G n
a ~x;~y :=
( a :=
Clearly, A 0 is order-equivalent to an N 0 \Theta N 0 -submatrix of J \Gamma 2M ORT p
n . We prove that
For each x 2 G n
p we have
It is easy to see, that this expression is independent from x. It remains to show that for
~x 6= ~y holds Obviously
where u; v; w are the numbers of vectors ~z 2 G n
p that are, respectively, orthogonal to both,
to none, and to exactly one of ~x and ~y. Lemma 21 and some lines of routine checking show,
that indeed
The claim follows from Corollary 17 now.
proof of Theorem
1. It is known that c prob (SEQ n
Hence by Proposition 20 follows SEQ 2 PP cc n MODmP cc . On the other hand, for
a prime factor of m, it follows from Lemma 4, Corollary 7, and Proposition 22 that
2. It is known that c n (SEQ n it is easy to see that c co-n (SEQ n
O(log n). Hence NP cc 6' co-NP cc and, by considering the negated functions, co-NP cc 6'
NP cc . But PP cc is closed under complement by Lemma 3. To prove that NP cc is
contained in PP cc , consider a protocol P of complexity t that computes some language
in the nondeterministic acceptance mode. Protocol obviously computes the
same language probabilistically.
8 Relations between modular classes
Proposition 23 Let p, q primes with p 6= q. Then
c mod p (ORT q
for infinitely many n:
proof: By Proposition 12 it is sufficient to show that
rank IF q
As in Section 7 let G n
p be a maximal set of pairwise linear independent vectors of IF n
and consider the submatrix M 0 of M ORT p
indexed by vectors in G n
. Remember N
We prove that, for infinitely many n,
and, hence, has rank
For the moment consider M 0 as integer matrix. Since
we obtain
a
else
Consequently, M 0 is a matrix of the form
a
. b
b .
Let B be the N 0 \Theta N 0 matrix whose entries are all equal to b and let I N 0 be the N 0 \Theta N 0
identity matrix. The characteristic polynomial of B is
Therefore M 02 is invertible if and only if p(b \Gamma a) 6j 0 mod q. But since
the latter is the case if and only if
For n with
holds Indeed, due to Fermat's
Little Theorem we have
for the infinitely many n 2 IN satisfying (2).
Proposition 23 together with Lemma 4 yields
Theorem 24 Let p and q be two different prime numbers, and let m be a multiple of pq.
1. MOD p P cc and MOD q P cc are incomparable with regard to inclusion.
2. MOD p P cc is properly contained in MODmP cc .
9 Nondeterminism versus modularity
Proposition 25 Let p be prime. Then
proof: By Proposition 13 it is sufficient to show that
rank IB
Again, we represent each 1-dimensional subspace of IF n
p by a non-zero vector and consider
the N 0 \Theta N 0 submatrix M 0 of M ORT p
indexed by elements from G n
.
Recall that a 0-1-matrix has Boolean rank 1 if there are sets A and B of rows and column,
such that the entries inside A \Theta B are equal to 1 and all other entries are equal to 0. Let
be a 1-homogeneous submatrix of M 0 , i.e., a submatrix whose entries are equal to
1. Since ORT p
vectors ~x from
the linear subspace L(B) generated by B. Consequently, the vectors ~a 2 A are elements of
the orthogonal complement L(B) ? of L(B). Hence,
with
we can estimate, for even n, the size of each 1-homogeneous submatrix of M 0 by
Now we are done. The number of 1-entries in M 0 equals
We have
rank IB
since each 1-entry of M 0 has to be covered by at least one 1-homogeneous submatrix of M 0 .
The next proposition is based on the well-known fact that we can interchange the rows
and the columns of the matrix M SDT n in such a way that we get a triangular matrix with
1's in its main diagonal (see [14]).
Proposition 26 Let p be a prime number. Then
Theorem be a positive natural number, and p be a prime number. Then
1. NP cc and MOD p P cc as well as co-NP cc and MOD p P cc are incomparable with respect to
inclusion.
2. co-NP cc and MODmP cc are incomparable with respect to inclusion.
proof:
1. By Corollary 7 and Proposition 25 and 26 we know that
2. It is easy to see that c co-n (SEQ n n). Hence, by Proposition 20
On the other hand, let q be a prime number such that qjm. Then by Lemma 4 and by
Proposition
Let p and q be distinct primes and m ? 0 a multiple of p \Delta q. The known relations between
the counting communication complexity classes considered in this paper are shown in the
following picture. Solid lines between classes indicate containment and dotted lines indicate
non-comparability.
MODmP cc
MOD q P cc
To complete the picture the following problems remain open:
1. For prime m the class MODmP cc is closed under complement. Is this true also for
composite m?
2. Let m 1
properly contained in



--R

On notions of information transfer in VLSI circuits

Complexity classes in communication complexity theory

Relations among Thresholds
On different modes of communication
Relations between communication complexity classes
On the power of small-depth
Branching programs provide lower bounds on the area of multilective deterministic and nondeterministic VLSI circuits
Geometric arguments yield better bounds for

On oblivious branching programs of linear length
Variation ranks of communication matrices and lower bounds for depth two circuits having symmetric gates with unbounded fan-in
Communication complexity: a survey
Las Vegas is better than determinism in VLSI and distributed computing
Monotone circuits for matching require linear Depth
On interpolation by analytic functions with special properties and some weak lower bounds on the size of circuits with symmetric gates
New York and Basel
Lower bounds by probabilistic arguments

--TR
Meanders and their applications in lower bounds arguments
Relations between communication complexity classes
Monotone circuits for matching require linear depth
Relativized counting classes
Complexity classes defined by counting quantifiers
On oblivious branching programs of linear length
Branching programs provide lower bounds on the areas of multilective deterministic and nondeterministic VLSI-circuits
Multiparty protocols, pseudorandom generators for logspace, and time-space trade-offs
Non-deterministic communication complexity with few witnesses
Geometric arguments yield better bounds for threshold circuits and distributed computing
Communication complexity
Spectral methods for matrix rigidity with applications to size-depth tradeoffs and communication complexity
Las Vegas is better than determinism in VLSI and distributed computing (Extended Abstract)
On notions of information transfer in VLSI circuits

--CTR
Henrik Brosenne , Carsten Damm , Matthias Homeister , Stephan Waack, On approximation by -OBDDs, Information Processing Letters, v.102 n.1, p.17-21, April, 2007
Henrik Brosenne , Matthias Homeister , Stephan Waack, Nondeterministic ordered binary decision diagrams with repeated tests and various modes of acceptance, Information Processing Letters, v.98 n.1, p.6-10, 15 April 2006
modularity;protocol;upper bound;probabilism;non-determinism;lower bound;communication complexity class