Authors Paul Beame, Matei David, Toniann Pitassi, Philipp Woelfel,
License CC-BY-3.0
T HEORY OF C OMPUTING, Volume 6 (2010), pp. 201–225
www.theoryofcomputing.org
Separating Deterministic from Randomized
Multiparty Communication Complexity
Paul Beame∗ Matei David† Toniann Pitassi‡ Philipp Woelfel§
Received: September 5, 2008; published: November 15, 2010.
Abstract: We solve some fundamental problems in the number-on-forehead (NOF) k-
player communication model. We show that there exists a function which has at most
logarithmic communication complexity for randomized protocols with one-sided false-
positives error probability of 1/3, but which has linear communication complexity for
deterministic protocols and, in fact, even for the more powerful nondeterministic protocols.
The result holds for every ε > 0 and every k ≤ 2(1−ε)n players, where n is the number of
bits on each player’s forehead. As a consequence, we obtain the NOF communication class
separation coRP 6⊂ NP. This in particular implies that P 6= RP and NP 6= coNP. We also
show that for every ε > 0 and every k ≤ n1−ε , there exists a function which has constant
randomized complexity for public coin protocols but at least logarithmic complexity for
private coin protocols. No larger gap between private and public coin protocols is possible.
Our lower bounds are existential; no explicit function is known to satisfy nontrivial
lower bounds for k ≥ log n players. However, for every ε > 0 and every k ≤ (1 − ε) · log n
players, the NP 6= coNP separation (and even the coNP 6⊂ MA separation) was obtained
independently by Gavinsky and Sherstov (2010) using an explicit construction. In this
work, for k ≤ (1/9) · log n players, we exhibit an explicit function which has communication
∗ Supported by NSF grant CCR-0514870
† Supported by NSF grant CCF-0832797
‡ Supported by NSERC
§ Supported by NSERC and DFG grant WO 1232/1-1
ACM Classification: F.1.3
AMS Classification: 68Q15
Key words and phrases: communication complexity, number on forehead
2010 Paul Beame, Matei David, Toniann Pitassi, and Philipp Woelfel
Licensed under a Creative Commons Attribution License DOI: 10.4086/toc.2010.v006a009
PAUL B EAME , M ATEI DAVID , T ONIANN P ITASSI , AND P HILIPP W OELFEL
complexity O (1) for public coin protocols and Ω (log n) for deterministic protocols. This
improves the best previously known deterministic lower bound for a function with efficient
randomized protocols, which was Ω (log log n), given by Beigel, Gasarch, and Glenn (2006).
It follows from our existential result that any function that is complete for the class
of functions with polylogarithmic nondeterministic k-player communication complexity
does not have polylogarithmic deterministic complexity. We show that the set intersection
function, which is complete in the number-in-hand model, is not complete in the NOF model
under cylindrical reductions.
1 Introduction
The question of how much communication is necessary in order to compute a function when its input
is distributed between several computationally unbounded players was introduced by Yao [26], and it
has since been shown to have many applications in diverse areas of computer science. The case of
k = 2 players has been studied extensively. In this paper we are interested in the case of k ≥ 3 players,
specifically in the ”number-on-forehead” (NOF) model, which was first considered by Chandra, Furst,
and Lipton [12]. In this model, the input is partitioned into k parts, so that player i can see all parts
except for the ith part (since it is “written on his forehead”). The standard reference on communication
complexity is the text by Kushilevitz and Nisan [18].
The NOF communication model is a fascinating and complex model that is not well understood when
k ≥ 3. The complexity of the situation arises from the fact that every part of the input is seen by multiple
players. As the number of players increases, the sharing becomes increasingly generous. During the
execution of a protocol, the set of inputs consistent with a particular message sequence is described by a
so-called cylinder intersection. The combinatorial structure of cylinder intersections appears difficult to
understand.
Lower bounds for multiparty complexity in the NOF model are connected to a major open problem in
complexity theory; in a series of papers by Yao [27], Beigel and Tarui [10], and Håstad and Goldman [16],
it was established that superlogarithmic communication complexity lower bounds in the NOF model
for any explicit function with polylogarithmically many players would imply explicit lower bounds
for ACC0 . The best lower bound knownfor an explicit function was given by Babai, Nisan, and
Szegedy [4], and it is of the form Ω n/2k , so it breaks down when the number of players is greater
than logarithmic. Lower bounds in this model have many other important applications as well, including:
constructions of pseudorandom generators for space bounded computation, constructions of universal
traversal sequences, time-space trade-offs [4], further circuit complexity bounds [16, 23, 22], and proof
complexity bounds [8, 6].
The motivation for our work is to pursue a broader understanding of the NOF complexity model.
In particular, we would like to answer some of the basic questions that are still open for this model,
but have well-known solutions in the 2-player model. For k ≥ 3, we consider the three usual versions
of communication complexity: deterministic, randomized, and nondeterministic complexity. Are there
functions separating these three different complexity measures? Nothing was known in this sense prior to
the preliminary version of this work [5], even for k = 3 players.
T HEORY OF C OMPUTING, Volume 6 (2010), pp. 201–225 202
D ETERMINISTIC VS . R ANDOMIZED M ULTIPARTY C OMMUNICATION C OMPLEXITY
Our main result is that for every ε > 0 and every k ≤ 2(1−ε)n , there is a function with n bits on
each players’ forehead that is computable with logarithmic communication by a randomized k-player
NOF communication protocol with bounded one-sided false-positives error, but which requires linear
amount of communication for deterministic protocols, and in fact, even for nondeterministic (unbounded
false-negatives error) protocols. We obtain this result nonconstructively by showing that nondeterministic
protocols for a certain class of “graph functions” have a nice normal form and then establishing a lower
bound for such functions via a counting argument over protocols in normal form. Communication
cc
complexity classes such as Pcc k and NPk were introduced for k = 2 players by Babai, Frankl, and
Simon [1]; we generalize these concepts to k ≥ 3 players, and we infer the following separation: coRPcc k 6⊂
NPcck . In particular, this implies P cc 6= RPcc and NPcc 6= coNPcc . As a corollary of our lower bound, we
k k k k
also establish an optimal separation between the powers of public- and private-coin randomized NOF
protocols, albeit only for k ≤ n1−ε (for every ε > 0).
The lower bound above is nonconstructive, but for k at most logarithmic in the input size, we also
give explicit families of graph functions with NOF communication complexity O (1) for public-coin
randomized protocols and Ω (log n) for deterministic protocols. (We believe that the latter is, in fact,
super-polylogarithmic.) The best previously known deterministic lower bound for a function with efficient
randomized NOF protocols is the Ω (log log n) lower bound given by Beigel, Gasarch, and Glenn [9] for
the Exact-T function, which was originally investigated in [12] in the special case of k = 3 players. As
a corollary, we also obtain the fact that the function families we define have Ω (log log n) private-coin
randomized NOF communication complexity but only O (1) public-coin randomized NOF communication
complexity.
The problem of separating deterministic from nondeterministic NOF communication complexity is
particularly interesting because of its connection to proof complexity. It was shown by Beame, Pitassi,
and Segerlind [8] that for k = 3, (log n)Ω(1) lower bounds on the randomized NOF complexity of set
intersection, which has nondeterministic NOF complexity O (log n), would imply lower bounds for
polynomial threshold proof systems, such as the Lovász-Schrijver proof systems, as well as the Chvátal
cutting planes proof system. This brings us to our second question: is there a “complete” problem for the
class of problems with efficient NOF nondeterministic algorithms under a suitable notion of reduction?
Given our separation result, such a function would automatically be hard for deterministic protocols.
Following [1], it is not hard to see that set intersection is complete under communication-free reductions
for the number-in-hand (NIH) model. (The NIH model is an alternative generalization of the 2-player
model in which each player gets his part of the input in his hand, and thus each player sees only his own
part.) We prove that under communication-free reductions, set intersection is not complete in the NOF
model.
Subsequent to the preliminary version of this paper [5], in a series of works by Lee and Shraib-
man [19], Chattopadhyay and Ada [13], and Beame and Huynh [7], lower bounds were obtained for
the randomized complexity of the set disjointness function for k ≤ O (log n)1/3 players, implying the
NOF communication complexity class separation NPcc cc cc cc
k 6⊂ BPPk , and therefore RPk 6= NPk . David,
Pitassi, and Viola [14] improve this separation using a different function, for every ε > 0 and every
k ≤ (1 − ε) log n players. See the excellent survey article by Sherstov [25] for more details on this line of
work.
Independently of our work and using different techniques, Gavinsky and Sherstov [15] obtained the
T HEORY OF C OMPUTING, Volume 6 (2010), pp. 201–225 203
PAUL B EAME , M ATEI DAVID , T ONIANN P ITASSI , AND P HILIPP W OELFEL
coNPcc cc cc cc
k 6⊂ MAk separation, which also implies the NPk 6= coNPk separation. Their results are based on
an explicit construction, and they hold for every ε > 0 and every k < (1 − ε) log n players.
2 Definitions and preliminaries
Let k : N → N be a non-decreasing function controlling the number of players as a function of the input
size n. In general, we write k instead of k(n) when the input size n is clear from the context.
In the NOF multiparty communication complexity model of computation [12] there are k players,
numbered 1 through k, that compute a function fk,n : X1 × · · · × Xk → {0, 1}, where each Xi is a set of size
at most 2n . For each 1 ≤ i ≤ k, an input xi ∈ Xi is (metaphorically) placed on the forehead of player i.
Thus, player i knows the values of all of the inputs except for xi .
The players exchange bits according to an agreed-upon protocol, by writing them on a public
blackboard. A protocol specifies solely as a function of the blackboard contents: whether or not the
communication is over; if it is over, the output of the protocol; and if it is not over, the next player to
speak. A protocol also specifies what each player communicates as a function of the blackboard contents
and of the inputs seen by that player. The cost of a protocol is the maximum number of bits written on
the blackboard.
In a deterministic protocol, the blackboard is initially empty. A public-coin randomized protocol of
cost c is simply a probability distribution over deterministic protocols of cost c, which can be viewed as a
protocol in which the players have access to a shared random string that is not counted towards the cost.
A private-coin randomized protocol is a protocol in which each player has access to a private random
string. A nondeterministic protocol is a randomized private coin protocol with one-sided error (only false
negatives) and error probability less than 1.
The deterministic communication complexity of fk,n , written Dk ( fk,n ), is the minimum cost of a
pub
deterministic protocol for fk,n that always outputs the correct answer. For 0 ≤ ε < 1/2, let Rk,ε ( fk,n )
denote the minimum cost of a public-coin randomized protocol for fk,n which, for every input, makes
an error with probability at most ε (over the choice of the deterministic protocols). The public-coin
pub pub
randomized communication complexity of fk,n is Rk ( fk,n ) = Rk,1/3 ( fk,n ). Let Rk,ε ( fk,n ) denote the
minimum cost of a private-coin randomized protocol for fk,n which, for every input, makes an error
with probability at most ε (over the choice of the private random strings). The private-coin randomized
communication complexity of fk,n is Rk ( fk,n ) = Rk,1/3 ( fk,n ). For both public-coin and private-coin
complexities we add a superscript 1 if we require that the protocol errs only on 1-inputs (i. e., false-
negatives), and superscript 0 if we require that the protocol errs only on 0-inputs (i. e., false-positives).
0,pub
For example, Rk,ε ( fk,n ) is the minimum cost of a k-player public-coin protocol for fk,n which is
always correct on 1-inputs and errs with probability at most ε on every 0-input. The nondeterministic
communication complexity of fk,n , written Nk ( fk,n ), is the minimum cost of a nondeterministic protocol
for fk,n .
In general, we consider a function family f = ( fk(n),n ) defined for all but finitely many n, and we are
interested in how the communication complexity of the functions in the family grows with the input size
n. When n is clear from the context, we drop the subscripts and we write f instead of fk,n . Thus, for any
of the complexity measures C defined above, we write Ck ( f ) for Ck ( fk(n),n ), which is itself a function
of n.
T HEORY OF C OMPUTING, Volume 6 (2010), pp. 201–225 204
D ETERMINISTIC VS . R ANDOMIZED M ULTIPARTY C OMMUNICATION C OMPLEXITY
Since the general model laid out above is very powerful, we are also interested in communication
restrictions. A player is oblivious in a certain protocol if the message he writes on the board is a function
of the inputs he sees, but not a function of the messages sent by other players. Since we are interested
in the best protocol, we may safely assume that all oblivious players write first, and then non-oblivious
players continue to communicate using the information written by the former. A protocol in which all
players are oblivious is called simultaneous. The simultaneous multiparty model was studied by Babai et
al. [2], who proved new lower bounds, as well as surprising upper bounds in this model.
Since any function fk,n can be computed using only n + 1 bits of communication, following [1], for
a family of functions f = ( fk,n ), communication protocols are considered “efficient” or “polynomial”
if only polylogarithmically many bits are exchanged. Accordingly, let Pcc k denote the class of function
O(1) cc
families f for which Dk ( f ) ≤ (log n) , let NPk denote the class of function families f for which
Nk ( f ) ≤ (log n)O(1) , and let RPcc k denote the class of function families f for which R1k ( f ) ≤ (log n)O(1) .
cc cc cc
The classes BPPk , coRPk and coNPk can be defined similarly to their computational complexity
counterparts.
The following are some important function families.
Definition 2.1. The equality function family is EQ = EQ2,n , where EQ2,n : ({0, 1}n )2 → {0, 1} is
defined by setting EQ2,n (x1 , x2 ) = 1 if x1 = x2 . The set intersection function family is SetInt = (SetIntk,n ),
where SetIntk,n : ({0, 1}n )k → {0, 1} is defined by setting SetIntk,n (x1 , . . . , xk ) = 1 if there exists some
j ∈ [n] such that x1, j = · · · = xk, j = 1.
Following [4], cylinder intersections have played an important role in multiparty communication
complexity lower bounds.
Definition 2.2. An i-cylinder Ci ⊆ X1 × · · · × Xk is a set such that for all x1 ∈ X1 , . . . , xk ∈ Xk , xi0 ∈ Xi we
have (x1 , . . . , xi , . . . , xk ) ∈ Ci if and only if (x1 , . . . , xi0 , . . . , xk ) ∈ Ci . For a set S ⊆ X1 × · · · × Xi−1 × Xi+1 ×
· · · × Xk , we say that S is the foot of the i-cylinder Ci if for every x−i = (x1 , . . . , xi−1 , xi+1 , . . . , xk ), x−i ∈ S
if and only if there exists xi ∈ Xi such that (x1 , . . . , xk ) ∈ Ci .
A cylinder intersection is a set of the form C = ki=1 Ci where each Ci is an i-cylinder in X1 × · · · × Xk .
T
3 Non-constructive separations
3.1 Graph functions, representations, and a normal form
We are interested in a special type of Boolean functions for which we can show that deterministic
protocols can be put in a restrictive “normal form,” where player 1 is oblivious and every other player
sends only 1 bit.
Definition 3.1. Let X1 , . . . , Xk be sets. Let g : X2 × · · · × Xk → X1 be a function. Let graphg : X1 × X2 ×
· · · × Xk → {0, 1} be the function defined by setting graphg (x1 , x2 , . . . , xk ) = 1 if g(x2 , . . . , xk ) = x1 . We
say that graphg is the graph function of g. In general, we say that f is a graph function if f = graphg for
some g.
We observe the following easy facts.
T HEORY OF C OMPUTING, Volume 6 (2010), pp. 201–225 205
PAUL B EAME , M ATEI DAVID , T ONIANN P ITASSI , AND P HILIPP W OELFEL
Fact 3.2. A function f : X1 × · · · × Xk → {0, 1} is a graph function if and only if for all (x2 , . . . , xk ) ∈
X2 × . . . × Xk , there exists exactly one x1 ∈ X1 such that f (x1 , x2 , . . . , xk ) = 1. Furthermore, a function
g completely determines the graph function graphg , and conversely, a graph function f completely
determines a function g such that f = graphg .
If f is a graph function, then it is reducible with no communication to 2-player n-bit equality EQ2,n :
player 1 computes the unique value x1∗ for the input on its forehead for which the output is 1, and player 2
sees the real input x1 ; players 1 and 2 now run an equality testing protocol on (x1∗ , x1 ). We know that
0,pub
R02,1/n (EQ2,n ) ≤ O (log n) and R2 (EQ2,n ) = Θ (1) [18]. Therefore, we obtain the following.
0,pub
Lemma 3.3. For every graph function family f = ( fk,n ), we have R0k,1/n ( f ) ≤ O (log n) and Rk (f) =
Θ (1). In particular, f ∈ coRPcc
k .
The following theorem shows that a nondeterministic protocol for a graph function can be put in a
special normal form: the nondeterminism is removed, player 1 acts obliviously, and all other players
simply send a check bit.
Theorem 3.4. Let f be a graph function. Let P be a nondeterministic protocol for f , with cost d. Then,
there exists a deterministic protocol P0 for f such that:
• player 1 first sends d bits obliviously;
• next, all other players simultaneously send one “check” bit each;
• the output of the protocol is 1 if and only if all check bits are 1.
Proof. Let X1 × · · · × Xk be the domain of f . By Fact 3.2, there is a unique function g such that
f = graphg . This can be computed by all players without communication, as it does not depend on the
input. Furthermore, it is well known that if f has a d-bit nondeterministic protocol, then there exists a
cover of the 1-inputs of f by a family of 2d monochromatic cylinder intersections. Let I` | ` ∈ {0, 1}d
be such a cover. For every `, let I` = I`1 ∩ · · · ∩ I`k , where I`i is an i-cylinder.
We describe the protocol P0 on input x = (x1 , x2 , . . . , xk ). First, player 1 computes x1∗ = g(x2 , . . . , xk ).
Next, player 1 computes some index ` ∈ {0, 1}d such that (x1∗ , x2 , . . . , xk ) ∈ I` . Such an index exists
because (x1∗ , x2 , . . . , xk ) is a 1-input of f . Player 1 communicates ` on d bits. Then, every other player i
communicates a check bit which is equal to 1 if and only if the input (x1 , x2 , . . . , xi−1 , xi+1 , . . . , xk ) seen
by player i belongs to the foot of the i-cylinder I`i . The output of P0 is 1 if and only if all check bits are 1.
We argue that P0 is correct. Assume f (x) = 1. By definition of a graph function, x1∗ = x1 . Then,
clearly (x1 , x2 , . . . , xk ) = (x1∗ , x2 , . . . , xk ) ∈ I` , so all check bits are 1, and P0 outputs 1. Conversely, assume
all check bits are 1. We claim x ∈ I` = I`1 ∩ I`2 ∩ · · · ∩ I`k . For every i ≥ 2, the fact that x ∈ I`i follows from
the fact that the check bit sent by player i is 1. Lastly, observe that (x1 , x2 , . . . , xk ) ∈ I`1 if and only if
(x1∗ , x2 , . . . , xk ) ∈ I`1 , because membership in I`1 cannot depend on the first coordinate. But the latter holds
by construction of I` . Hence, x ∈ I` and thus f (x) = 1.
T HEORY OF C OMPUTING, Volume 6 (2010), pp. 201–225 206
D ETERMINISTIC VS . R ANDOMIZED M ULTIPARTY C OMMUNICATION C OMPLEXITY
3.2 Separating randomized and deterministic protocols
In the following, we consider a class of functions which have logarithmic communication complexity
for private-coin randomized protocols with bounded one-sided error. Using Theorem 3.4, we give an
upper bound on the number of functions that have an efficient deterministic protocol. Since this number
is smaller than the total number of functions, we conclude that some function in that class has linear
deterministic communication complexity.
For integers k ≥ 2 and m, n ≥ 1, let Gk−1,n,m be the set of all functions g : ({0, 1}n )k−1 → {0, 1}m .
The following Lemma is the heart of our counting argument.
Lemma 3.5. Let ε > 0 and let k = k(n) satisfy k ≤ 2(1−ε)n for all large n. Let m = m(n) := b(n − log k)/2c.
There exists a function gk−1,n ∈ Gk−1,n,m such that the function family f = ( fk,n ) defined by fk,n =
graphgk−1,n satisfies m − 1 ≤ Nk ( f ) ≤ R1k ( f ) ≤ Dk ( f ) ≤ n + 1 for all large n.
/ NPcc
Observe that for the function family above, (ε/2)n − 1 ≤ m ≤ n, so Nk ( f ) ≥ Ω (n), and f ∈ k .
m n k−1 cc
Also, fk,n is a graph function on {0, 1} × ({0, 1} ) , so by Lemma 3.3, f ∈ coRPk . Our main result
follows.
Corollary 3.6. For every ε > 0 and for every k = k(n) satisfying k ≤ 2(1−ε)n for all large n, we have
coRPcc cc cc cc cc
k 6⊂ NPk . In particular, Pk 6= RPk and NPk 6= coNPk .
cc
Proof of Lemma 3.5. A function g ∈ Gk−1,n,m has a domain ({0, 1}n )k−1 and range {0, 1}m . Therefore,
it is impossible to encode every such function on less than m · 2(k−1)n bits. Moreover, by Fact 3.2, for
0
g 6= g0 , we have graphg 6= graphg .
Let d = d(n) be the minimum value such that for all g ∈ Gk−1,n,m , graphg has nondeterministic
communication complexity N(graphg ) ≤ d. By Theorem 3.4, for every such g, there exists a deterministic
protocol P0 over {0, 1}m × ({0, 1}n )k−1 computing graphg in the normal form given in Theorem 3.4.
Every such protocol is completely specified by a function governing player 1 with domain ({0, 1}n )k−1
and range {0, 1}d , and k − 1 other functions, each one governing a distinct player i > 1, with domain
{0, 1}m × ({0, 1}n )k−2 × {0, 1}d and range {0, 1}. These functions uniquely determine the protocol P0 ,
which in turn uniquely determines graphg (because P0 is correct on every input), which in turn uniquely
determines g. Therefore, we can encode every g ∈ Gk−1,n,m on at most d · 2(k−1)n + (k − 1) · 2m+d+(k−2)n
bits.
Putting the upper and lower bounds together, we obtain
d · 2(k−1)n + (k − 1) · 2m+d+(k−2)n ≥ m · 2(k−1)n .
This is equivalent to 2d ≥ (m − d) · 2n−m−log(k−1) . Hence, d ≥ min{m, n − m − log(k − 1)}. Using
m = b(n − log k)/2c, we get d ≥ m − 1. Trivially, d ≤ R1k ( f ) ≤ Dk ( f ) ≤ n + 1.
3.3 Separating public-coin and private-coin protocols
We now consider the difference between public-coin and private-coin randomized protocols. Trivially, any
pub
private-coin protocol can be simulated by tossing the coins in public, so for all f and k, Rk ( f ) ≤ Rk ( f ).
In the other direction, Newman [21] provides a simulation of a public-coin protocol by a private-coin
protocol. (Although it is stated for the special case of 2 players, the proof still works if the number of
players satisfies k = k(n) ≤ nO(1) .)
T HEORY OF C OMPUTING, Volume 6 (2010), pp. 201–225 207
PAUL B EAME , M ATEI DAVID , T ONIANN P ITASSI , AND P HILIPP W OELFEL
Proposition 3.7 ([21]). Suppose that k = k(n) ≤ nO(1) . For every function f : {0, 1}kn → {0, 1}, we have
pub
Rk ( f ) ≤ Rk ( f ) + O (log n).
We see that the maximum possible gap between the public-coin and private-coin randomized com-
plexities of f is an additive Θ (log n). A natural question that arises is whether there is a function that
achieves this gap. (In the special case of k = 2 players, this is achieved by the equality function.) Our
results allow us to answer this question affirmatively. To obtain the lower bounds, we need the following
extension of Lemma 3.8 in [18] to k players.
Lemma 3.8. For every ε > 0, for every k = k(n), and for every function family f = ( fk,n ) such that
Dk ( fk,n ) ≥ ω (1) and k = k(n) ≤ O Dk ( f )1−ε , we have Rk ( f ) ≥ Ω (log Dk ( f )).
Before proving Lemma 3.8, we complete the separation of public-coin and private-coin protocols.
Corollary 3.9. For every ε > 0 and for every k = k(n) satisfying k ≤ n1−ε for all large n, there exists a
pub
function family f = ( fk,n ) such that Rk ( f ) = Θ (1) and Rk ( f ) = Θ (log n).
Proof of Corollary 3.9. By Lemma 3.5 there is a family of graph functions f such that
b(n − log k)/2c − 1 ≤ Dk ( f ) ≤ n + 1 .
Since k ≤ n for all large n, we get that n/2 ≤ Dk ( f ) for all large n. Now using the stronger assumption
k ≤ n1−ε , we get k ≤ 21−ε · Dk ( f )
1−ε for all large n. Observe that the 21−ε factor does not depend on n,
hence k ≤ O Dk ( f ) 1−ε . We can now apply Lemma 3.8, obtaining Rk ( f ) ≥ Ω (log n). By Lemma 3.3,
pub
Rk ( f ) ≤ O (log n) and Rk ( f ) = Θ (1).
Proof of Lemma 3.8. We claim the following holds. For every n,
Rk,ε 0 ( f ) 1 0
Dk ( f ) ≤ (k − 1) · 2 · 1 + log(k − 1) − log − ε + Rk,ε ( f ) .
0 (3.1)
2
We first complete the proof of the Lemma using the statement above. Assume it is not the case that
Rk ( f ) ≥ Ω (log Dk ( f )), so Rk ( f ) ≤ ε/2 · log Dk ( f ) for infinitely many n. Using the fact that Rk ( f ) =
Rk,1/3 ( f ), the assumption that k ≤ c · Dk ( f )1−ε for some constant c and all large n, and Equation 3.1
above, we get that for infinitely many n,
ε
Dk ( f ) ≤ c · Dk ( f )1−ε · Dk ( f )ε/2 · 1 + (1 − ε) · log Dk ( f ) + · log Dk ( f )
2
1−(ε/2)
≤ 3 · c · Dk ( f ) · log Dk ( f ) .
Since ε > 0 and Dk ( f ) ≥ ω (1), this is a contradiction. Hence, Rk ( f ) ≥ Ω (log Dk ( f )).
The proof of Equation 3.1 follows the same idea as the proof of Lemma 3.8 in [18]. Let c = Rk,ε 0 ( fk,n )
and consider the ε 0 -error randomized protocol P that achieves communication cost c. Without loss of
generality, assume that P always halts after exactly c bits are communicated. Let
t = 1 + log(k − 1) − log(1/2 − ε 0 ) + c .
T HEORY OF C OMPUTING, Volume 6 (2010), pp. 201–225 208
D ETERMINISTIC VS . R ANDOMIZED M ULTIPARTY C OMMUNICATION C OMPLEXITY
We construct a deterministic protocol P0 for fk,n of cost (k − 1) · 2c · t as follows.
For every player i and every string ` ∈ {0, 1}c , let pi (`) denote the probability player i responds
consistently with the transcript (blackboard content) ` (over their own private random strings). Player i
(for 1 ≤ i ≤ k − 1) computes, for every `, the real number pi (`) and publishes p∗i (`), a t-bit approximation
of pi (`). This introduces an error of at most φ = 2−t for every such value.
Player k now computes, for every `, the value ∏k−1 ∗
i=1 pi (`) · pk (`). Since
p∗i (`) ∈ {pi (`) − φ , pi (`) + φ }
and since pi (`) ≤ 1, we get
! ( )
k−1 k k
∏ p∗i (`) · pk (`) ∈ ∏ pi (`) − ((1 + φ )k−1 − 1), ∏ pi (`) + ((1 + φ )k−1 − 1) .
i=1 i=1 i=1
Each transcript of the randomized protocol is associated with an output (0 or 1). Player k now estimates
the probability of an output in the randomized protocol by summing over the estimates of the probabilities
for each transcript corresponding to that output. Finally, player k decides to output in P0 the value that
has a probability higher than 1/2.
In the original protocol P, an error is made with probability at most ε 0 . For the deterministic simulation
to work, we need to make sure that the extra error introduced by the rounding process is less than 1/2 − ε 0 .
Since each estimate has error at most (1 + φ )k−1 − 1 and there are at most 2c leaves, we need to make
sure that 2c · ((1 + φ )k−1 − 1) < (1/2 − ε 0 ). Equivalently, we need (1 + φ )k−1 < 1 + (1/2 − ε 0 )/2c .
We choose
1/2 − ε 0
t = 1 + log(k − 1) − log(1/2 − ε 0 ) + c , so φ = 2−t = .
2 · (k − 1) · 2c
We know that, for 0 ≤ x < 1/2, we have
k−1
x
1+ ≤ ex ≤ 1 + 2 · x .
k−1
Moreover, (1/2 − ε 0 )/(2 · 2c ) < 1/2. Therefore,
1/2 − ε 0
(1 + φ )k−1 < 1 + 2 · = 1 + (1/2 − ε 0 )/2c .
2 · 2c
This shows P0 is correct, completing the proof of the Lemma.
4 Lower bounds for explicit graph functions
The separation coRPcc cc
k 6⊂ NPk in Section 3.2 is nonconstructive. It would be interesting to achieve
this separation, or even the weaker coRPcc cc
k 6⊂ Pk , with an explicit family of functions, even for k = 3
players. In this section, we give two constructions of explicit families of graph functions (thus, in coRPcc
k
by Lemma 3.3) that, we believe, might be outside Pcc k for k ≥ 3. While we are unable to prove the
T HEORY OF C OMPUTING, Volume 6 (2010), pp. 201–225 209
PAUL B EAME , M ATEI DAVID , T ONIANN P ITASSI , AND P HILIPP W OELFEL
super-polylogarithmic ((log n)ω(1) ) deterministic communication complexity lower bounds required to
place them outside Pcc k , we are able to prove much weaker logarithmic (Ω (log n)) lower bounds. As a
corollary, we obtain a separation between deterministic and public-coin randomized complexities for
explicit families of graph functions, though this is much weaker than our conjecture.
We begin in Section 4.1 by developing a method for representing graph functions with efficient
deterministic protocols. In Section 4.2, we give a family of graph functions for the case where we have
only k = 3 players. This construction does not immediately generalize for k > 3 players, but we present it
first because it is both simple enough and illustrative of a certain “mixing” property (made precise later)
that plays a crucial role in our arguments. We then prove the lower bound Dk ( f ) ≥ Ω (log n) for, in fact,
any function family f that satisfies this mixing property. In Section 4.3, we present a different family of
graph functions, that can be defined for every k = k(n) with 3 ≤ k ≤ (1/9) · log n, and we show that this
family satisfies the same mixing property used in Section 4.2, thus yielding a similar lower bound.
4.1 Representing graph functions by colorings and cylinder intersections
Most lower bound proofs for Dk ( f ) use the fact shown in [4] that any k-player protocol with complexity
d for a function f yields a partition of the input into O 2d cylinder intersections on which f is constant.
For k ≥ 3 players, the known techniques for proving lower bounds on the number of cylinder intersections
needed for such a partition are discrepancy-based and inherently yield lower bounds even for randomized
protocols. Therefore, these techniques are not suitable for proving good lower bounds for functions with
low randomized communication complexity. For graph functions we obtain different, although related
structures. These structures seem to be better suited for lower bound proofs for functions in RPcc k , as they
allow us to prove an Ω (n) non-explicit lower bound in Lemma 3.5, as well as an Ω (log n) explicit lower
bound in Section 4.
Throughout this section, f : X1 × · · · × Xk → {0, 1} is a graph function. Using Fact 3.2, let g :
g
X2 × · · · × Xk → X1 be the unique function such that f = graph . For any natural number D and a set S, a
D-coloring of S is a mapping c : S → [D]. We identify 2d = {1, . . . , 2d } with {0, 1}d .
Assume that f can be computed by a d-bit protocol P. The special protocol P0 for f , derived in
Theorem 3.4, can be characterized by a coloring of X2 × · · · × Xk and cylinder intersections in X2 × · · · × Xk ,
as follows. Let c be the 2d -coloring of X2 × · · · × Xk , where c(x2 , . . . , xk ) is the message Alice sends in P0 if
she sees (x2 , . . . , xk ). Consider a fixed message ` from Alice and a fixed value a ∈ X1 on Alice’s forehead.
The subset of points in X2 × · · · × Xk for which all other players accept if they see a on Alice’s forehead
and receive message ` is a cylinder intersection I`,a . Note, each such cylinder intersection I`,a may also
contain points that are not colored `. However, it is not possible that a point p = (x2 , . . . , xk ) ∈ I`,a has
color ` but g(p) 6= a because then Alice would send message ` if she saw p and the other players would all
accept if they saw a on Alice’s forehead. Hence, (a, x2 , . . . , xk ) would be accepted by P0 , a contradiction.
This proves the following.
Lemma 4.1. Let f : X1 × · · · × Xk → {0, 1} be a graph function. Assume f has a deterministic protocol
of cost d. Then, there exist:
• a 2d -coloring c of X2 × · · · × Xk and
• a collection of cylinder intersections I`,a ⊆ X2 × · · · × Xk | ` ∈ {0, 1}d , a ∈ X1 ,
T HEORY OF C OMPUTING, Volume 6 (2010), pp. 201–225 210
D ETERMINISTIC VS . R ANDOMIZED M ULTIPARTY C OMMUNICATION C OMPLEXITY
such that
∀x = (x1 , x2 , . . . , xk ) ∈ X1 × X2 × · · · × Xk f (x) = 1 ⇐⇒ (x2 , . . . , xk ) ∈ Ic(x2 ,...,xk ),x1 .
In particular, I`,a contains all points y ∈ X2 × · · · × Xk with color c(y) = ` and f (a, y) = 1, but no
point y0 with color c(y0 ) = ` and f (a, y0 ) = 0.
4.2 A function family for 3 players
In the case of k = 3 players, our construction is based on universal families of hash functions, introduced
by Carter and Wegman [11]. We begin with an informal description of our arguments.
Definition 4.2 ([11]). Let A, B be sets, and let H = {h : A → B} be a family of functions from A to B. We
say that H is a universal family of hash functions if for every x1 6= x2 ∈ A and for every y1 , y2 ∈ B, we
have
1
Pr [h(x1 ) = y1 and h(x2 ) = y2 ] = 2 .
h∈H |B|
Given a universal family H of hash functions from A to B, our three-player function f is defined on
the set B × H × A as follows. The second player holds a hash function h ∈ H, the third player holds an
input x ∈ A, and h(x) ∈ B is the unique value for the input of the first player that makes f evaluate to 1.
The key “mixing” property that this construction satisfies is closely related to the Hash Mixing Lemma
obtained by Mansour, Nisan, and Tiwari [20].
Lemma 4.3 ([20, Lemma 13]). Let H = {h : A → B} be a universal family of hash functions. Let A0 ⊆ A,
B0 ⊆ B, and H 0 ⊆ H. Then,
s
|B 0| |H| · |B0 |
0
Pr h(x) ∈ B − ≤ .
x∈A0 ,h∈H 0 |B| |A0 | · |H 0 | · |B|
Informally, this says that, for every large rectangle R ⊆ H × A and every b ∈ B, if we visualize R
as a matrix where the entry at location (h, x) has value h(x), then the number of b-valued entries in R
is very close to uniform, that is, |R|/|B|. After making these definitions precise, we use the mixing
property combined with the characterization of a deterministic protocol for f from Lemma 4.1, to give
some evidence as to why we believe Dk ( f ) might be large. We subsequently prove in Theorem 4.8 that
Dk ( f ) ≥ Ω (log n) for any function f that satisfies the mixing property.
Definition of the family We write Fq for the finite field of q elements when q is a prime power. Let
n ≥ 4 be a positive integer, and let m = n1/2 . For x ∈ {0, 1}n and a ∈ {0, 1}n+m−1 , let a ◦ x (the
convolution of a and x) be the m-bit string z whose i-th bit is defined by zi = ∑nj=1 x j a(i−1)+ j mod 2. For
two bit strings z and b, let z ⊕ b be the bitwise exclusive-or of the two strings. For (a, b) ∈ F2n+m−1 × F2m ,
let ha,b : F2n → F2m be defined by ha,b (x) = (a ◦ x) ⊕ b. Then, Hn,m = { ha,b | a ∈ F2n+m−1 , b ∈ F2m } is a
universal family of hash functions from F2n to F2m [20]. We are now ready to define our family of graph
functions for k = 3 players.
T HEORY OF C OMPUTING, Volume 6 (2010), pp. 201–225 211
PAUL B EAME , M ATEI DAVID , T ONIANN P ITASSI , AND P HILIPP W OELFEL
Definition 4.4. Let f =
( f3,n
) be the family of functions defined as follows. For n large enough, let
0
n0 = bn/2c and let m = n1/2 . Let f3,n : F2m × Hn ,m × F2n0 → {0, 1} be defined by setting f3,n (y, h, x) = 1
if y = h(x).
0 0 0
Observe that |F2m | = 2m ≤ 2n , |Hn ,m | = 2n +2m−1 ≤ 2n for large n, and |F2n0 | = 2n ≤ 2n , so they can
all be embedded as subsets of {0, 1}n . Clearly, f3,n is a graph function, so by Lemma 3.3,
0,pub
R03,1/n ( f ) ≤ O (log n) and R3 ( f ) = Θ (1) .
Mixing property The following is a “mixing” property of f , that we use to prove lower bounds on
D3 ( f ).
Definition 4.5 (Mixing Property). Let f = ( fk,n )n∈N be a family of graph functions. Let m = dlog |X1 |e.
Note that, in general, k = k(n) and m = m(n). Let Z = X2 × · · · × Xk . Writing f for fk,n , let g be the
unique function such that f = f g , as given by Fact 3.2.
We say that the family f has a mixing property if the following holds. For large enough n, for
every cylinder intersection I ⊆ Z with |I| ≥ |Z| · 2−2m , and for every x1 ∈ X1 , when (x2 , . . . , xk ) is drawn
uniformly from I,
1
Pr[g(x2 , . . . , xk ) = x1 ] ≤ 2 · m = 2−m+1 .
2
Intuitively, if g were a true random function, we’d have Pr [g(x2 , . . . , xk ) = x1 ] = 2−m for every x1 and
every S. The mixing property says that f g looks “almost random” on any “large” cylinder intersection.
Note. In the condition |I| ≥ |Z| · 2−2m , the choice of −2m as an exponent might seem arbitrary. As it
is, Definition 4.5 allows us to prove Theorem 4.8. But, in fact, for both the construction in this section,
and for the construction in Section 4.3, we could prove an even stronger mixing property, one that would
apply to even smaller rectangles: for every α, for large enough n (now a function of α), for every cylinder
intersection I with |I| ≥ |Z| · 2−αm , the same property as above would be required of I. However, we
do not know how to use this stronger mixing property to prove a larger lower bound than the one in
Theorem 4.8.
In the special case when f is the family from Definition 4.4, we have k = 3, so we can visualize
0 0
Z = Hn ,m ×F2n0 as a 2-dimensional matrix in which rows correspond to hash functions h ∈ Hn ,m , columns
correspond to inputs x ∈ F2n0 , and the entry at row h and column x is Zh,x = h(x) ∈ F2m . Furthermore,
cylinder intersections in 2 dimensions are rectangles. With this interpretation, the mixing property says
that for every large rectangle R ⊆ Z, more precisely, when |R| ≥ |Z| · 2−m , the number of y-entries in R is
at most twice the expected number if R was filled at random with values from F2m . The fact that f has
this property follows directly from Lemma 4.3.
Lemma 4.6. The function family f = ( f3,n )n∈N from Definition 4.4 has the mixing property from Defini-
tion 4.5.
0
Proof. Since H n ,m is a universal family of hash functions, by Lemma 4.3, for every rectangle R ⊆ Z and
for every y ∈ F2m , when (h, x) are drawn uniformly from R, we have
0
!1/2
|H n ,m | |Z| −n0 −m 1/2
1 −m
Pr [h(x) = y] ≤ + =2 + ·2 .
|F2m | |R| · |F2m | |R|
T HEORY OF C OMPUTING, Volume 6 (2010), pp. 201–225 212
D ETERMINISTIC VS . R ANDOMIZED M ULTIPARTY C OMMUNICATION C OMPLEXITY
0
When |R| ≥ |Z| · 2−2m , as in Definition 4.5, we have Pr [h(x) = y] ≤ 2−m + 2−n /2+m/2 . Since n0 /2 ≥ 3m/2
for large enough n, we get Pr [h(x) = y] ≤ 2−m+1 .
Evidence towards a conjecture Let f = ( f3,n ) be the function family from Definition 4.4. The
following is not a precise argument, but here is why we believe that the deterministic communication
complexity of f might be large.
We write f for f3,n . Let d = D3 ( f ). By Lemma 4.1, there exists a 2d -coloring c of Z and there are
2 d+m rectangles R`,y ⊆ M, for ` ∈ [2d ] and y ∈ F2m , such that
∀(y, h, x) ∈ Fm × H n,m × Fn : (h, x) ∈ Rc(h,x),y ⇔ h(x) = y .
In keeping with the matrix interpretation of Z, we say that (h, x) is an (`, y)-entry in Z if c(h, x) = ` and
h(x) = y.
Definition 4.7. For a subset S ⊆ Z, let #(`,y) (S) denote the number of (`, y)-entries in S and let ρ(`,y) (S) =
#(`,y) (S)/|S| denote the density of (`, y)-entries in S. We use the notation (`, ·) and (·, y) to refer to all
entries with color ` and all entries with value y, respectively.
For every (`, y) ∈ [2d ] × F2m , let
[
B`,y = R`,y \ R`,y0 .
y0 6=y
We call this set the boundary of the rectangle R`,y . Note that, by definition of the coloring, all (`, y)-entries
in Z are in B`,y .
The entries in Z are colored with 2d colors. Let red be a “popular” color, in the sense that ρ(red,·) (Z) ≥
1/2d . When y is chosen uniformly at random from F2m ,
#(red,·) (Z) |Z|
E #(·,y) (Bred,y ) ≥ E #(red,y) (Bred,y ) = E #(red,y) (Z) = ≥ m+d .
2m 2
Furthermore, for various y, the sets Bred,y are disjoint, so
|Z|
E [|Bred,y |] ≤ .
2m
If we fixed a y for which both quantities above are within constant factors of their expectations (this
is imprecise, but we believe it could be made precise), we would obtain a pair (red, y) such that
ρ(·,y) (Bred,y ) ≥ Ω 1/2d , whereas the mixing property (Definition 4.5) says that, if Rred,y is large enough,
ρ(·,y) (Rred,y ) ≤ O (1/2m ). The smaller d is, the larger the gap between these numbers. The reason this
situation does not immediately translate into a lower bound for d in terms of m is that Bred,y is far from a
rectangle, so its density of (·, y)-entries could be much larger than that of the rectangle Rred,y . However,
we also consider this as evidence that d might have to be large.
T HEORY OF C OMPUTING, Volume 6 (2010), pp. 201–225 213
PAUL B EAME , M ATEI DAVID , T ONIANN P ITASSI , AND P HILIPP W OELFEL
A weaker lower bound In the following Theorem, we show that every family of graph functions f =
( fk,n ) that satisfies the mixing property from Definition 4.5 has deterministic communication complexity
at least logarithmic in m = m(n) = dlog |X1 |e, the size of the input of player 1.
We describe the proof idea for the case of k = 3 players, when we can view Z as a matrix, but the
proof itself works in general for k ≥ 3. Let d = D3 ( f ) and consider the 2d -coloring c of the matrix Z
given by Lemma 4.1. The proof proceeds by inductively decreasing the number of colors available and
shrinking the matrix. During each step, we introduce a number of “holes” in the matrix (entries that are
colored in the original matrix with one of the removed colors). We show that eventually there are no
colors left to use, but the matrix still does not consist only of holes.
To see the limitation of this technique, note that even if we were able to shrink the matrix by, say, a
factor of 2 in order to remove every color, there are still 2d colors to remove, so at the end we would have
d O(1)
shrunk the matrix by a factor of 22 . Since the matrix Z has size 2m , this technique can only produce
lower bounds of the form d ≥ Ω (log m).
Theorem 4.8. Let f = ( fk,n ) be a family of graph functions, with fk,n : X1 × · · · × Xk → {0, 1}, that
satisfies the mixing property in Definition 4.5. Let m = m(n) = dlog |X1 |e be the size of the input of
player 1. Then, Dk ( fk,n ) ≥ Ω (log m).
Proof. We write f for fk,n . Let d = Dk ( f ). Let Z = X2 × · · · × Xk . Using Fact 3.2, let g : Z → X1 be
the unique function such that f = f g . By Lemma 4.1, there is a 2d -coloring c of Z and there are 2d+m
cylinder intersections I`,y , for (`, y) ∈ [2d ] × X1 , such that
∀(y, x2 , . . . , xk ) ∈ X1 × Z, (x2 , . . . , xk ) ∈ Ic(x2 ,...,xk ),y ⇐⇒ g(x2 , . . . , xk ) = y .
We say that a point (x2 , . . . , xk ) has color c(x2 , . . . , xk ) and value g(x2 , . . . , xk ). For a set S ⊆ Z, let #(`,y) (S)
denote the number of points (x2 , . . . , xk ) ∈ S with color ` and value y.
Assume there exists some ε < 1 such that for all m, d ≤ ε · log m. We will derive a contradiction.
For large enough m, we prove by induction that for all 0 ≤ i ≤ 2d , there exists a cylinder intersection
Ii ⊆ Z and a set of “holes” Hi ⊆ Ii such that:
• |Ii | ≥ |Z| · 2−i(d+2) ;
• |Hi | ≤ i · |Z| · 2−m+1 ; and
• the initial coloring induces a coloring of the points in Ii \ Hi with 2d − i colors.
Assuming we have established this inductive statement, letting i = 2d , we see that we must have I2d \H2d =
0,
/ for any points in this set would have been uncolored in the original coloring. For large enough m,
d
|I2d | ≥ |Z| · 2−2 (d+2) ≥ |Z| · 2−m (ε·log m+2) > |Z| · 2−m+ε·log m+1 ≥ |Z| · 2−m+d+1 .
ε
Since |H2d | ≤ 2d · |Z| · 2−m+1 , we get I2d \ H2d 6= 0,
/ which is a contradiction.
We now prove the inductive statement. For i = 0, let I0 = Z and let H0 = 0. / Then, c is a coloring of
I0 \ H0 with 2d colors.
Next, assume the inductive statement is true for some 0 ≤ i < 2d . We have
|Ii \ Hi | ≥ |Z| · 2−i(d+2) − i · 2−m+1 > |Z| · 2−i(d+2) − 2−m+d+1 > |Z| · 2−i(d+2)−1 ,
T HEORY OF C OMPUTING, Volume 6 (2010), pp. 201–225 214
D ETERMINISTIC VS . R ANDOMIZED M ULTIPARTY C OMMUNICATION C OMPLEXITY
where in the last inequality we used m − d − 1 > mε (ε · log m + 2) > i(d + 2), for large enough m.
Let (`, y) be the most popular color-value pair in Ii \ Hi . There are at most 2m+d such pairs, so
#(`,y) (Ii \ Hi ) ≥ |Ii \ Hi | · 2−m−d ≥ |Z| · 2−i(d+2)−1−m−d = |Z| · 2−(i+1)(d+2)−m+1 .
Let Ii+1 = Ii ∩ I`,y , which is a cylinder intersection in Z because both Ii and I`,y are. By the property of the
coloring c in Lemma 4.1, all points in Z with color-value (`, y) are in I`,y . Hence,
|Ii+1 | ≥ #(`,y) (Ii \ Hi ) ≥ |Z| · 2−(i+1)(d+2)−m+1 .
Note that (i + 1)(d + 2) − 1 ≤ mε (ε log m + 2) − 1 < m, so |Ii+1 | ≥ |Z| · 2−2m . Then, by the mixing
property in Definition 4.5, #(·,y) (Ii+1 )/|Ii+1 | ≤ 2−m+1 , so |Ii+1 | ≥ #(·,y) (Ii+1 ) · 2m−1 . Also, #(·,y) (Ii+1 ) ≥
#(`,y) (Ii+1 ) ≥ #(`,y) (Ii \ Hi ). Putting these together, we get
|Ii+1 | ≥ #(`,y) (Ii \ Hi ) · 2m−1 ≥ |Z| · 2−(i+1)(d+2)−m+1 · 2m−1 = |Z| · 2−(i+1)(d+2) ,
establishing the first part of the inductive statement.
Let Hi+1 = Hi ∪ {(x2 , . . . , xk ) ∈ Ii+1 | c(x2 , . . . , xk ) = `}. By the induction hypothesis, points in Ii \ Hi
are colored with at most 2d − i colors. Since ` is no longer available, we see that all points left in
Ii+1 \ Hi+1 must now be colored with at most 2d − i − 1 colors, establishing the third part of the inductive
statement.
Finally, by the property of c in Lemma 4.1, all points in I`,y that have color ` must have value y. In
the entire set Z, by the mixing property, there are at most |Z| · 2−m+1 points with value y. Then,
|Hi+1 | ≤ |Hi | + |Z| · 2−m+1 ≤ (i + 1) · |Z| · 2−m+1 ,
establishing the second part of the inductive statement.
Corollary 4.9. The function family f from Definition 4.4 satisfies D3 ( f ) ≥ Ω (log n). Furthermore,
pub
f provides a separation between public-coin and private-coin complexities, as R3 ( f ) ≤ O (1) and
R3 ( f ) ≥ Ω (log log n).
Proof. By Lemma 4.6, f has the mixing property. By Theorem 4.8, D3 ( f ) ≥ Ω (log m). By definition of
f , m = (n/3)1/2 , so D3 ( f ) ≥ Ω (log n). Since the family f consists of graph functions, by Lemma 3.3,
pub
R3 ( f ) ≤ O (1). Finally, by Lemma 3.8, R3 ( f ) ≥ Ω (log log n).
4.3 A function family for 3 or more players
In the case of k ≥ 3 players, the family of graph functions we construct is based on the generalized inner
product function GIPF over a finite field F. It turns out that the crucial “mixing property” in Definition 4.5
follows quite easily from a bound on the “strong discrepancy” of GIPF obtained by Babai, Hayes, and
Kimmel [3].
T HEORY OF C OMPUTING, Volume 6 (2010), pp. 201–225 215
PAUL B EAME , M ATEI DAVID , T ONIANN P ITASSI , AND P HILIPP W OELFEL
Following [3], for a non-Boolean function f : Z → B and a set S ⊆ Z, the strong discrepancy of f on
S is defined as follows:1
1 |S|
disc∗ ( f , S) := max · | f −1 (y) ∩ S| −
y∈B |Z| |B|
|S| 1
= max · Pr [ f (z) = y] − .
y∈B |Z| z∼S |B|
This measure considers all possible function values y ∈ B, and it reflects the largest difference between
the actual number of y-inputs in S and the average number of such inputs if f were perfectly balanced on
S. It is not hard to see that strong discrepancy is connected to the mixing property from Definition 4.5.
Before making this connection formal, we define the function we will be using.
Definition 4.10. For integers n ≥ 1, k ≥ 2, and for a finite field F, the generalized inner product function
over F, GIPFk,n : (Fn )k → F, is defined as follows. For 1 ≤ i ≤ k, let xi = (xi,1 , . . . , xi,n ) ∈ Fn , where for
1 ≤ j ≤ n, xi, j ∈ F. Then, !
n k
GIPFk,n (x1 , . . . , xk ) := ∑ ∏ xi, j .
j=1 i=1
In [3], the following upper bound is obtained on the strong discrepancy of this function.
p
Fact 4.11 ([3]2 ). Let n, m ≥ 1 and p ≥ 2. For every cylinder intersection I ⊆ ((F2m )n ) ,
!n·21−p
1 p−1
∗
F 2m 1
disc GIP p,n , I ≤ 1 − m · 1 − 1 − m .
2 2
The following is the family of graph functions we use for k ≥ 3 players.
Definition 4.12. Let k = k(n) ≥ 3 be some function, let n0 = n0 (n) := bn1/2 c, and let m = m(n) := bn1/4 c.
0
Let V = (F2m )n . Let f = ( fk,n ) be the function family where fk,n : F2m × V k−1 → {0, 1} is defined by
2m
setting fk,n (x1 , x2 , . . . , xk ) = 1 if GIPFk−1,n0 (x2 , . . . , xk ) = x1 .
m
We claim that the small strong discrepancy of GIPFk−1,n
2
0 implies that f satisfies the mixing property
from Definition 4.5.
Lemma 4.13. If k = k(n) satisfies 3 ≤ k ≤ (1/9) · log n, then the function family f from Definition 4.12
has the mixing property from Definition 4.5.
Proof of Lemma 4.13. Let I ⊆ V k−1 be a cylinder intersection with |I| ≥ |V k−1 | · 2−2m and let y ∈ F2m .
We want to show that h i
Pr 2m
GIPFk−1,n0 (z 2 , . . . , z k ) = y ≤ 2−m+1 .
(z2 ,...,zk )∼I
1 We note that strong discrepancy when |B| = 2 and regular (Boolean) discrepancy are off by a factor of 2. To get them to
agree, we’d have to multiply strong discrepancy by |B|. In here, we simply use the definition given in [3].
2 In [3], this fact is not stated as a stand-alone lemma, but it is proved and used as part of the proof of Corollary 4.12.
T HEORY OF C OMPUTING, Volume 6 (2010), pp. 201–225 216
D ETERMINISTIC VS . R ANDOMIZED M ULTIPARTY C OMMUNICATION C OMPLEXITY
m
Writing z for (z2 , . . . , zk ) and g for GIPFk−1,n
2
0 , from the definition of strong discrepancy we get
1 |V k−1 |
Pr [g(z) = y] − ≤ · disc∗ (g, I)
z∼I 2m |I|
≤ 22m · disc∗ (g, I) .
By Fact 4.11 (with p = k − 1),
!n0 ·22−k
1 k−2
∗ 1
disc (g, I) ≤ 1 − m · 1 − 1 − m
2 2
!n0 ·22−k
1 k−2
≤ 1− 1− m (since m ≥ 1)
2
!
1 k−2 0 2−k
≤ exp − 1 − m ·n ·2 (using 1 − x ≤ e−x )
2
1 0 2−k
≤ exp − k−2 · n · 2 (since 1 − 1/2m ≥ 1/2)
2
0 −2k
= 2−16·(log e)·n ·2 .
Putting everything together,
1
Pr [g(z) = y] ≤ + 22m · disc∗ (g, I)
z∼U(I) 2m
0 −2k
≤ 2−m + 22m−16·(log e)·n ·2
≤ 2−m + 2−m = 2−m+1 (for large enough n).
Above, we need n0 ≥ (3 · m · 22k )/(16 · log e). Since log n0 ≥ (1/2) · log n − 1, log m ≤ (1/4) · log n and
2k ≤ (2/9) · log n < (1/4) · log n, the inequality holds for large enough n.
Corollary 4.14. For every function k = k(n) such that 3 ≤ k ≤ (1/9) · log n, the function family f from
Definition 4.12 satisfies Dk ( fk,n ) ≥ Ω (log n). Furthermore, f separates public-coin and private-coin
pub
randomized protocols, as Rk ( fk,n ) ≤ O (1) and Rk ( fk,n ) ≥ Ω (log log n).
Proof. By Lemma 4.13 and Theorem 4.8, Dk ( fk,n ) ≥ Ω (log m). Since m = bn1/4 c, Dk ( fk,n ) ≥ Ω (log n).
pub
Since Fk,n is a graph function, by Lemma 3.3, Rk ( fk,n ) ≤ O (1). Finally, by Lemma 3.8, Rk ( fk,n ) ≥
Ω (log log n).
5 On complete problems
cc
An alternative approach to separating Pcc
k from RPk with an explicit function is to find a function that
is complete in some sense. If we can prove for some explicit function that it is “at least as hard” as any
T HEORY OF C OMPUTING, Volume 6 (2010), pp. 201–225 217
PAUL B EAME , M ATEI DAVID , T ONIANN P ITASSI , AND P HILIPP W OELFEL
function in RPcc cc
k , then by our separation result we can conclude that it is not in Pk . The set intersection
cc
function is complete for the class analogous to NPk in the number-in-hand (NIH) model, and thus also
for NPcc cc
2 . In this section, we prove that this function is not complete for NPk for k ≥ 3.
In two-player communication complexity, Babai, Frankl, and Simon [1] defined a natural notion of a
reduction between problems called a “rectangular” reduction that does not require any communication to
compute, as well as an appropriate “polynomially-bounded” version of rectangular reduction for function
families.
Definition 5.1 ([1]). Let f : X1 × X2 → {0, 1} and g : X10 × X20 → {0, 1}. A pair of functions (ϕ1 , ϕ2 ) with
ϕi : Xi → Xi0 is a rectangular reduction of f to g, written f v g, if f (x1 , x2 ) = g(ϕ1 (x1 ), ϕ2 (x2 )). For
function families f = { fn } and g = {gn } where fn , gn : ({0, 1}n )2 → {0, 1}, we write f v p g if there is a
O(1)
function m : N → N such that for every n, fn v gm(n) and m(n) is 2(log n) .
Proposition 5.2 ([1]). Let f and g be function families. If f v p g and g ∈ Pcc cc
2 then f ∈ P2 . If f v p g
and g ∈ NPcc cc
2 then f ∈ NP2 .
Definition 5.3. A function family g is complete for NPcc cc
2 under rectangular reductions if g ∈ NP2 and
cc
for all f ∈ NP2 , f v p g.
Recall the set intersection function SetInt from Definition 2.1 Clearly, SetInt ∈ NPcc
k . In [1] it was
observed that:
Proposition 5.4 ([1]). SetInt is complete for NPcc
2 under rectangular reductions.
For k ≥ 3, rectangular reductions extend to cubic reductions in the NIH model of communication
complexity. Moreover, it is easy to see that the completeness result of Proposition 5.4 continues to hold
in the NIH model under cubic reductions. One might expect that SetInt is also complete for NPcck under a
natural extension of rectangular reductions in the NOF model. Such a notion of reduction should not
require any communication between the players. This yields the following definition:
Definition 5.5. Given f : X1 × · · · × Xk → {0, 1} and g : X10 × · · · × Xk0 → {0, 1}, we say that a k-tuple of
functions (ϕ1 , . . . , ϕk ) is a cylindrical reduction of f to g if for every (x1 , . . . , xk ) ∈ X1 × · · · × Xk there
is an (x10 , . . . , xk0 ) ∈ X10 × · · · × Xk0 such that ϕi (x1 , . . . , xi−1 , xi+1 , . . . , xk ) = (x10 , . . . , xi−1
0 , x0 , . . . , x0 ) for all
i+1 k
i ∈ [k], and f (x1 , . . . , xk ) = g(x10 , . . . , xk0 ). Thus, each ϕi maps the NOF view of the i-th player on input
(x1 , . . . , xk ) for f to the NOF view of the i-th player on input (x10 , . . . , xk0 ) for g.
We show that cylindrical reductions must be of a very special form, given by the natural no-commu-
nication reductions associated with the number-in-hand model.
Definition 5.6. Given f : X1 × · · · × Xk → {0, 1} and g : X10 × · · · × Xk0 → {0, 1}, we say that a k-tuple
of functions (ψ1 , . . . , ψk ) is a cubic reduction of f to g if ψi : Xi → Xi0 for every i, and f (x1 , . . . , xk ) =
g(ψ1 (x1 ), . . . , ψk (xk )).
Lemma 5.7. If (ϕ1 , . . . , ϕk ) is a cylindrical reduction of f to g then there is a cubic reduction (ψ1 , . . . , ψk )
of f to g such that, for all i,
ϕi (x1 , . . . , xi−1 , xi+1 , . . . , xk ) = (ψ1 (x1 ), . . . , ψi−1 (xi−1 ), ψi+1 (xi+1 ), . . . , ψk (xk )).
T HEORY OF C OMPUTING, Volume 6 (2010), pp. 201–225 218
D ETERMINISTIC VS . R ANDOMIZED M ULTIPARTY C OMMUNICATION C OMPLEXITY
Proof. We prove by induction on k that any consistent cylindrical reduction (whether or not it correctly
reduces f to g) must be cubic. The claim is trivial for k = 2. Assume that k > 2. Consider (x1 , . . . , xk )
and let (x10 , . . . , xk0 ) be the output of the cylindrical reduction on x. Let yk ∈ Xk . The requirement that
ϕk (x1 , . . . , xk−1 ) = (x10 , . . . , xk−1
0 ) and the fact that the views output by the ϕi for i < k must be consistent
with this output implies that for i < k,
ϕi (x1 , . . . , xi−1 , xi+1 , . . . , xk−1 , xk ) = (x10 , . . . , xi−1
0 0
, xi+1 0
, . . . , xk−1 , xk0 )
and
ϕi (x1 , . . . , xi−1 , xi+1 , . . . , xk−1 , yk ) = (x10 , . . . , xi−1
0 0
, xi+1 0
, . . . , xk−1 , y0k )
for some y0k ∈ Xk . Thus the first k − 2 coordinates of the output of ϕi are independent of the last coordinate
of its input. Since x = (x1 , . . . , xk ) and yk were chosen arbitrarily, for any such input we can define
functions (ϕ10 , . . . , ϕk−1 0 ) where ϕ 0 (x , . . . , x
i 1 i−1 , xi+1 , . . . , xk−1 ) consists of the first k − 2 coordinates of
ϕi (x1 , . . . , xi−1 , xi+1 , . . . , xk−1 , yk ) for any yk ∈ Xk . These form a consistent map on k − 1 coordinates and
therefore by the inductive hypothesis there are (ψ1 , . . . , ψk−1 ) such that
ϕi0 (x1 , . . . , xi−1 , xi+1 , . . . , xk−1 ) = (ψ1 (x1 ), . . . , ψi−1 (xi−1 ), ψi+1 (xi+1 ), . . . , ψk−1 (xk−1 ))
and therefore for i < k and any x1 , . . . , xk ∈ Xk ,
ϕi (x1 , . . . , xi−1 , xi+1 , . . . , xk−1 , xk ) = (ψ1 (x1 ), . . . , ψi−1 (xi−1 ), ψi+1 (xi+1 ), . . . , ψk−1 (xk−1 ), xk0 )
for some xk0 = φi (x1 , . . . , xi−1 , xi+1 , . . . , xk ) for some function φi ; i. e., ϕi acts componentwise on all but the
k-th coordinate. Now, since k > 2 there is some j ∈ / {i, k} and, by symmetry, the same inductive argument
can be applied to characterize ϕi for all i 6= j so that ϕi acts componentwise on all but the j-th coordinate.
Moreover, the inductive argument implies that there are functions ψ10 , . . . , ψ 0j−1 , ψ 0j+1 , . . . , ψk0 that give
this componentwise behavior. Defining ψ 0j = ψ j and ψk = ψk0 we see that we must have ψi0 = ψi for all
i ∈ [k]. Therefore,
ϕi (x1 , . . . , xi−1 , xi+1 , . . . , xk ) = (ψ1 (x1 ), . . . , ψi−1 (xi−1 ), ψi+1 (xi+1 ), . . . , ψk (xk ))
for i < k. Since k was arbitrarily chosen, the same applies for i = k and the result follows by induction.
Definition 5.8. The set A ⊆ X1 × · · · × Xk is a cube if A = A1 × · · · × Ak for some sets Ai ⊆ Xi , for all
i ∈ [k].
Lemma 5.9. If there is a cylindrical reduction of f : X1 × · · · × Xk → {0, 1} to SetIntk,m then f −1 (1) is a
union of m cubes.
Proof. By Lemma 5.7, there are functions (ψ1 , . . . , ψk ) such that
f (x1 , . . . , xk ) = SetIntk,m (ψ1 (x1 ), . . . , ψk (xk )) .
Thus (x1 , . . . , xk ) ∈ f −1 (1) if and only if there is some i ∈ [m] such that the i-th coordinate of each of
ψ1 (x1 ), . . . , ψk (xm ) is 1. For j ∈ [k] let Ai, j = {x j | the i-th coordinate of ψ j (x j ) is 1} ⊆ X j . Therefore
Ai,1 × · · · × Ai,k is a cube for each i ∈ [m] and f −1 (1) = i∈[m] Ai,1 × · · · × Ai,k as required.
S
T HEORY OF C OMPUTING, Volume 6 (2010), pp. 201–225 219
PAUL B EAME , M ATEI DAVID , T ONIANN P ITASSI , AND P HILIPP W OELFEL
Theorem 5.10. There is a function f : ({0, 1}n )3 → {0, 1} with deterministic 3-player NOF communica-
tion complexity at most 3 such that any cylindrical reduction of f to SetInt3,m requires m > 2n−3 .
Proof. For x, y, z ∈ {0, 1}n , define f (x, y, z) to be 1 if x, y, and z are pairwise orthogonal in Fn2 under
the standard dot product. There is a trivial 3-player NOF protocol for f in which 3 bits are exchanged,
namely, each player checks that the inputs it sees are orthogonal. We now show that any way to write
f −1 (1) as a union of cubes must contain exponentially many cubes since each cube can only cover an
exponentially small portion of f −1 (1).
For u, v ∈ {0, 1}n , let h(u, v) = 1 if hx, yi = 0 in Fn2 . Then f (x, y, z) = h(x, y)h(y, z)h(x, z). Consider
the uniform distribution µ over {0, 1}3n .
We first show that f −1 (1) is a set of probability more than 1/8. Under µ, for each pair u, v ∈ {x, y, z},
the probability that h(u, v) = 1 is 1/2 + 1/2n > 1/2 (consider whether or not u = 0n ). We claim that
the probability that f (x, y, z) = 1 is at least 1/8. Suppose that x 6= 0n . Then the probability that y is
orthogonal to x is precisely 1/2. Now, z is orthogonal to the span h{x, y}i with probability at least 1/4.
So, conditioned on x 6= 0n , the probability that f (x, y, z) = 1 is at least 1/8. If x = 0n then the probability
that f (x, y, z) = 1 is precisely the probability that y and z are orthogonal which is at least 1/2. Therefore
the probability that f (x, y, z) = 1 is more than 1/8 overall.
Now since f (x, y, z) = h(x, y)h(y, z)h(x, z), any cube C = A1 × A2 × A3 with C ⊆ f −1 (1) must, in
particular, have, A1 × A2 ⊆ h−1 (1). Thus every x ∈ A1 must be orthogonal to every y ∈ A2 and so the
dimensions of their spans must satisfy dim(hA1 i) + dim(hA2 i) ≤ n. Therefore
|A1 × A2 | ≤ |hA1 i × hA2 i| ≤ 2dim(hA1 i)+dim(hA2 i) ≤ 2n
so |C| ≤ 2n · |A3 | ≤ 22n and the probability that (x, y, z) ∈ C is at most 2−n . The claimed result follows
immediately.
This argument can be extended to other functions h : {0, 1}2n → {0, 1} that have only small 1-
monochromatic rectangles. It suffices that h(x, y)h(y, z)h(x, z) be 1 on a large fraction of inputs. Also,
although the above Lemma is stated only for k = 3 it is easy to see that the same bounds hold for larger k.
Given that any function f (x, y, z) of the form h1 (x, y)h2 (x, z)h3 (y, z) has communication complexity
at most 3, it seems unlikely that any function is complete for NPcc 3 under efficient reductions that do not
require communication.
6 Discussion
In this paper we give a nonconstructive separation of the NOF communication complexity classes Pcc k and
RPcck for up to k ≤ n O(1) players. We leave it as an open problem to exhibit an explicit function achieving
this separation, even for as few as k = 3 players.
To put the limitation on the number of players in perspective, we note that the only method for
proving any strong lower bound for an explicit function is the discrepancy method, and we only know
how to bound discrepancy in the case of up to k = log n players. Moreover, both the original discrepancy
method [4], and its recent generalizations [17, 24, 25] automatically yield lower bounds for randomized
protocols. It is an open problem to adapt these methods to proving deterministic lower bounds for
functions with efficient randomized protocols.
T HEORY OF C OMPUTING, Volume 6 (2010), pp. 201–225 220
D ETERMINISTIC VS . R ANDOMIZED M ULTIPARTY C OMMUNICATION C OMPLEXITY
Prior to this work, the best deterministic lower bound for a function with efficient randomized
protocols was Ω (log log n) for the Exact-T function [9]. In this paper, we improve this to an Ω (log n)
lower bound for two families of explicit functions, one based on universal families of hash functions, the
other on the generalized inner product function.
Perhaps surprisingly, some of the technical arguments we use in this paper bear a similarity to the ones
used by Babai, Hayes, and Kimmel [3]. In that paper, the goal was to obtain lower bounds for k-player
NOF protocols “with help.” These are protocols for non-Boolean functions g : ({0, 1}n )k → {0, 1}m ,
where at the start of the protocol, the players receive an (m − 1)-bit message from a benevolent helper
that sees the entire input. The result proved in that paper is discrepancy-based, so it works even for
randomized protocols with help, and it says that there are functions for which the best protocol with help
requires Ω(n/ck ) bits of communication, for some constant c.
Even though the results in [3] and the ones presented in this paper seem rather different, it turns out
that they are somewhat similar at the technical level. We have seen that if a function f g has a deterministic
protocol of cost c, then there is a 2c -coloring of the inputs to g, and cylinder intersections I`,x such that,
for every (color) `, (I`,x | x ∈ {0, 1}m ) partition the `-colored inputs to g. In contrast, if a function g
has a protocol with c bits of help and communication cost s, it can be shown that there are cylinder
intersections T`,x such that, for every (message/color) `, (T`,x | x ∈ {0, 1}s ) partition the entire set of inputs
to g. Notably, the latter partition is stricter than the former, because the sets corresponding to color ` can
no longer intersect on inputs which are not `-colored. In [3], a lower bound was obtained for the cost of a
protocol with help directly from the strong discrepancy of the function being computed. In this paper, we
are unable to derive a similar direct connection; instead, we use strong discrepancy indirectly, through the
Mixing Property in Definition 4.5, and we obtain weaker bounds.
It would also be interesting to study whether counting arguments can be used to separate other types
of protocols, for example, randomized from nondeterministic for the same type of one-sided error (i. e.,
RPcc cc
k 6= NPk ). Such a separation exists [14], but in [14], the number of players is limited to k < log n
because of its ultimate reliance on the iterated Cauchy-Schwarz scheme used to estimate discrepancy [4].
Potentially, a counting argument might avoid this limitation.
7 Acknowledgments
Originally, we stated Theorem 3.4 only for deterministic protocols. We are grateful to the anonymous
referees for pointing out that the original proof easily extends even to nondeterministic protocols.
References
[1] L ÁSZL Ó BABAI , P ÉTER F RANKL , AND J ÁNOS S IMON: Complexity classes in communication
complexity theory (preliminary version). In Proc. 27th FOCS, pp. 337–347. IEEE Comput. Soc.
Press, 1986. [doi:10.1109/SFCS.1986.15] 203, 205, 218
[2] L ÁSZL Ó BABAI , A NNA G ÁL , P ETER K IMMEL , AND S ATYANARAYANA L OKAM: Com-
munication complexity of simultaneous messages. SIAM J. Comput., 33(1):137–166, 2004.
[doi:10.1137/S0097539700375944] 205
T HEORY OF C OMPUTING, Volume 6 (2010), pp. 201–225 221
PAUL B EAME , M ATEI DAVID , T ONIANN P ITASSI , AND P HILIPP W OELFEL
[3] L ÁSZL Ó BABAI , T HOMAS H AYES , AND P ETER K IMMEL: The cost of the missing bit: Communi-
cation complexity with help. Combinatorica, 21(4):455–488, 2001. 215, 216, 221
[4] L ÁSZL Ó BABAI , N OAM N ISAN , AND M ÁRI Ó S ZEGEDY: Multiparty protocols, pseudorandom
generators for logspace, and time-space trade-offs. J. Comput. System Sci., 45(2):204–232, 1992.
[doi:10.1016/0022-0000(92)90047-M] 202, 205, 210, 220, 221
[5] PAUL B EAME , M ATEI DAVID , T ONIANN P ITASSI , AND P HILIPP W OELFEL: Separating deter-
ministic from nondeterministic NOF multiparty communication complexity. In Proc. 34th Intern.
Colloq. Autom. Lang. Program. (ICALP), volume 4596 of LNCS, pp. 134–145. Springer, 2007. 202,
203
[6] PAUL B EAME , T RINH H UYNH , AND T ONIANN P ITASSI: Hardness amplification in proof com-
plexity. In Proc. 42nd STOC, pp. 87–96. ACM Press, 2010. [doi:10.1145/1806689.1806703]
202
[7] PAUL B EAME AND DANG -T RINH H UYNH -N GOC: Multiparty communication complexity and
threshold circuit size of AC0 . In Proc. 50th FOCS, pp. 53–62. IEEE Comput. Soc. Press, 2009.
[doi:10.1109/FSCS.2009.12] 203
[8] PAUL B EAME , T ONIANN P ITASSI , AND NATHAN S EGERLIND: Lower bounds for Lovász–
Schrijver systems and beyond follow from multiparty communication complexity. SIAM J. Comput.,
37(3):845–869, 2007. [doi:10.1137/060654645] 202, 203
[9] R ICHARD B EIGEL , W ILLIAM G ASARCH , AND JAMES G LENN: The multiparty communi-
cation complexity of Exact-T: Improved bounds and new problems. In Proc. 31st. Intern.
Symp. Math. Found. Comput. Sci. (MFCS), volume 4162 of LNCS, pp. 146–156. Springer, 2006.
[doi:10.1007/11821069 13] 203, 221
[10] R ICHARD B EIGEL AND J UN TARUI: On ACC. Comput. Complexity, 4(4):350–366, 1994.
[doi:10.1007/BF01263423] 202
[11] J. L AWRENCE C ARTER AND M ARK N. W EGMAN: Universal classes of hash functions. J. Comput.
System Sci., 18(2):143–154, 1979. [doi:10.1016/0022-0000(79)90044-8] 211
[12] A SHOK K. C HANDRA , M ERRICK L. F URST, AND R ICHARD J. L IPTON: Multi-party protocols. In
Proc. 15th STOC, pp. 94–99. ACM Press, 1983. [doi:10.1145/800061.808737] 202, 203, 204
[13] A RKADEV C HATTOPADHYAY AND A NIL A DA: Multiparty communication complexity of dis-
jointness. Technical Report TR08-002, Electron. Colloq. on Comput. Complexity (ECCC), 2008.
203
[14] M ATEI DAVID , T ONIANN P ITASSI , AND E MANUELE V IOLA: Improved separations between
nondeterministic and randomized multiparty communication. ACM Trans. Comput. Log., 1(2):1–20,
2009. [doi:10.1145/1595391.1595392] 203, 221
T HEORY OF C OMPUTING, Volume 6 (2010), pp. 201–225 222
D ETERMINISTIC VS . R ANDOMIZED M ULTIPARTY C OMMUNICATION C OMPLEXITY
[15] D MITRY G AVINSKY AND A LEXANDER A. S HERSTOV: A separation of NP and coNP
in multiparty communication complexity. Theory of Computing, 6:227–245, 2010.
[doi:10.4086/toc2010.v006a010] 203
[16] J OHAN H ÅSTAD AND M IKAEL G OLDMANN: On the power of small-depth threshold circuits.
Comput. Complexity, 1(2):113–129, 1991. [doi:10.1007/BF01272517] 202
[17] H ARTMUT K LAUCK: Lower bounds for quantum communication complexity. SIAM J. Comput.,
37(1):20–46, 2007. [doi:10.1137/S0097539702405620] 220
[18] E YAL K USHILEVITZ AND N OAM N ISAN: Communication Complexity. Cambridge University
Press, 1997. 202, 206, 208
[19] T ROY L EE AND A DI S HRAIBMAN: Disjointness is hard in the multi-party number-on-the-forehead
model. In Proc. 23rd Comput. Complex. Conf. (CCC), pp. 81–91. IEEE Comput. Soc. Press, 2008.
[doi:10.1109/CCC.2008.29] 203
[20] Y ISHAY M ANSOUR , N OAM N ISAN , AND P RASOON T IWARI: The computational complexity of
universal hashing. Theoret. Comput. Sci., 107(1):121–133, 1993. [doi:10.1016/0304-3975(93)90257-
T] 211
[21] I LAN N EWMAN: Private vs. common random bits in communication complexity. Inform. Process.
Lett., 39(2):67–71, 1991. [doi:10.1016/0020-0190(91)90157-D] 207, 208
[22] N OAM N ISAN: The communication complexity of threshold gates. In Combinatorics, Paul Erdős
is Eighty, number 1 in Bolyai Society Mathematical Studies, pp. 301–315. J. Bolyai Math. Soc.,
Budapest, 1993. 202
[23] N OAM N ISAN AND AVI W IGDERSON: Rounds in communication complexity revisited. SIAM J.
Comput., 22(1):211–219, 1993. [doi:10.1137/0222016] 202
[24] A. A. R AZBOROV: Quantum communication complexity of symmetric predicates. Izv. Math.,
67(1):145–159, 2003. [doi:10.1070/IM2003v067n01ABEH000422] 220
[25] A LEXANDER A. S HERSTOV: Communication lower bounds using dual polynomials. Bull. Eur.
Assoc. Theor. Comput. Sci. EATCS, 95:59–93, 2008. 203, 220
[26] A NDREW C HI -C HIH YAO: Some complexity questions related to distributive computing (prelimi-
nary report). In Proc. 11th STOC, pp. 209–213. ACM Press, 1979. [doi:10.1145/800135.804414]
202
[27] A NDREW C HI -C HIH YAO: On ACC and threshold circuits. In Proc. 31st FOCS, volume 2, pp.
619–627, 1990. [doi:10.1109/FSCS.1990.89583] 202
T HEORY OF C OMPUTING, Volume 6 (2010), pp. 201–225 223
PAUL B EAME , M ATEI DAVID , T ONIANN P ITASSI , AND P HILIPP W OELFEL
AUTHORS
Paul Beame
professor
University of Washington, Seattle, WA
beame cs washington edu
http://www.cs.washington.edu/homes/beame/
Matei David
postdoctoral research fellow
Princeton University, Princeton, NJ
mateid cs princeton edu
http://www.cs.toronto.edu/~matei/
Toniann Pitassi
professor
University of Toronto, Toronto, ON
toni cs toronto edu
http://www.cs.toronto.edu/~toni/
Philipp Woelfel
assistant professor
University of Calgary, Calgary, AB
woelfel cpsc ucalgary ca
http://pages.cpsc.ucalgary.ca/~woelfel/
ABOUT THE AUTHORS
PAUL B EAME is a Professor of Computer Science & Engineering at the University of
Washington. He received his Ph. D. in Computer Science from the University of Toronto
in 1987 under the supervision of Stephen A. Cook. He is currently Chair of the IEEE
CS Technical Committee on the Mathematical Foundations of Computing. His research
has primarily focused on the complexity of concrete computational problems and proof
complexity, with a particular emphasis on complexity lower bounds.
M ATEI DAVID recently graduated from the University of Toronto; his advisor was fellow
coauthor Toniann Pitassi. In writing this, Matei realizes the relativity of the term
“recently.”
T HEORY OF C OMPUTING, Volume 6 (2010), pp. 201–225 224
D ETERMINISTIC VS . R ANDOMIZED M ULTIPARTY C OMMUNICATION C OMPLEXITY
T ONIANN P ITASSI is a professor at the University of Toronto, who still feels lucky to get
paid to do this. Hobbies include sculpting (where she is enthusiastic, but lacking in
talent), running (same skill set), and spending quality family time, which currently means
YouTube videos or Rummikub.
P HILIPP W OELFEL graduated in December 2003 from the University Dortmund under the
supervision of Ingo Wegener. In 2005 the German Research Foundation admitted him
to the Emmy-Noether Programme, which allowed him to meet two of his coauthors
during his Postdoctoral Fellowship (2005-2007) at the University of Toronto. Currently,
he is an Assistant Professor at the University of Calgary. His research interests include
computational complexity, randomized algorithms, and distributed computing.
T HEORY OF C OMPUTING, Volume 6 (2010), pp. 201–225 225