Communication Complexity and Applications Lecture #1: Spring, 2022

Communication Complexity and Applications

Lecturer: Toniann Pitassi

1 Introduction
In this course we will define the basic two-party model of communication, as introduced in the
seminal 1979 paper by Yao. We will discuss different measures of complexity for the basic model,
focusing mostly on deterministic, randomized and nondeterministic complexities of protocols. We
will introduce the very important set disjointness function and show that it has near maximal
communication complexity. We will also introduce extensions of the basic model to more than two
players– the number-in-hand model, as well as the number-on-forehead model. We will show lower
bounds for set disjointness in these models as well, as well as give a general discussion of lower
bound methods, and the state-of-the-art in terms of lower bounds.
We will then switch to discuss the many fundamental applications of communication complexity
for a variety of problems: data structures, streaming, privacy, machine learning, game theory,
extended formulations, proof complexity, distributed computing, and circuit lower bounds. We
will cover some recent applications in depth, with a particular focus on lower bounds for extended
formulations of linear programs.

2 The model
Let X, Y, Z be arbitrary finite sets and let f : X × Y → Z be an arbitrary function. There are
two players, Alice and Bob, who wish to compute the function f (x, y). The main obstacle is that
Alice only knows x and Bob only knows y. Thus, to compute the value f (x, y), they will need
to communicate with each other. We are assuming that they both follow a fixed protocol agreed
upon beforehand. The protocol consists of the players sending bits to each other until the value of
f can be determined.
We are only interested in the amount of communication between Alice and Bob, and we wish
to ignore the question of the internal computations of each player. Thus, we assume that Alice
and Bob have unlimited computational power. The cost of a protocol Π is the worst case cost of
Π over all inputs (x, y). The complexity of f is the minimum cost of a protocol that computes f .
Formally how do we specify a protocol? In each step one of the players sends one bit of
information to the other player. The bit depends on the input of the player who sends it, and all
the previous bits communicated so far.
In every step, a protocol specifies:

1. Which player sends the next bit;

2. Value of this bit (as a function of that players’ input, and history so far).

1
Communication Complexity and Applications Lecture #1: Spring, 2022

Without loss of generality, we can assume that the players always alternate, and that the last
bit sent is the value Π(x, y) output by the protocol. This only increases the length of the protocol
by a constant factor.
We say that a protocol Π computes a function f if for all x, y, f (x, y) = Π(x, y). Usually we
set X = Y = {0, 1}n , and Z = {0, 1}. In this case, the cost of a protocol, c(n), on inputs x, y, of
length n is the worst case cost of Π over all inputs of length n, and the communication complexity
of f is the minimum cost c(n) over all protocols that compute f .
Another view of a protocol which may be more convenient is the following:
Definition 1. A protocol Π over X × Y with range Z is a binary tree where each internal node
v is labelled either by a function av : X → {0, 1} or by a function bv : Y → {0, 1}1 , and each leaf
is labelled with an element of Z. The value of the protocol Π on input (x, y) is the label of the leaf
reached by starting from the root, and traversing the tree. The cost of the protocol Π on input (x, y)
is the length of the path on input (x, y). The cost of the protocol Π is the height of the tree.
A simple general protocol : Let any function f (x, y), with |x| = |y| = n. Alice sends x. Bob
sends f (x, y). The total communication is n+1 bits. Therefore, the (deterministic) communication
complexity of any boolean function is at most n + 1. However, for many functions, we can develop
much more efficient protocols, i.e., protocols with poly-logarithmic communication bits for specific
functions.
Next, we give some examples of functions that we will study in the up-coming lectures.
Example 1 (Parity). The parity function of (x, y) has value 1 if x, y have the same parity. A
simple protocol is the following: Alice sends the parity of x (1 if the number of 1’s in x is odd, and
0 otherwise). Then Bob replies 1 if and only if the parity of y is equal to the parity of x.
Parity is easy for deterministic communication.
Example 2 (Equality). Equality function: EQ(x, y) = 1 iff x = y.
We will see shortly that Equality requires maximal communication complexity (linear in n) but
has constant-cost randomized protocols.
Example 3 (Set disjointness). DISJ(x, y) = 1 iff there exists i such that xi = yi = 1. That is, we
think of x, y as characteristic vectors of subsets of [n] and we want to output 1 if the sets intersect,
and 0 of they are disjoint. A related problem is the set disjointness problem where x, y are subsets
of size k << n.
We will see in upcoming lectures that set disjointness requires linear randomized communication
complexity (and thus also linear deterministic communication complexity). However it has low cost
nondeterministic complexity. Set disjointness is the most important function in communication
complexity as it is complete for nondeterministic communication complexity, and therefore shares
the same important stature that the satisfiability problem (SAT) has in ordinary Turing machine
time complexity. However unlike SAT where is is a major open problem to prove (or disprove) that
SAT is not solvable in polynomial time, a major result in communication complexity establishes
that set disjointness is hard for deterministic and randomized complexity. We will cover two proofs
of this result later in the course. Nearly all of the applications of communication complexity that
we will discuss are obtained by reductions to the disjointness problem.
1
If a node is labelled by av intuitively means that Alice is sending a bit at this point, similarly for bv and Bob.

2
Communication Complexity and Applications Lecture #1: Spring, 2022

Pn
Example 4 (Inner product). The inner product function is defined as IP (x, y) = i=1 xi yi
(mod 2).

Example 5 (Clique versus Independent Set). Let G be a fixed undirected graph with n vertices.
Alice is given a subset S ⊂ [n] such that the vertices in S form a clique in G, and Bob is given a
subset T ⊂ [n] such that the vertices in T form an independent set in G. They want to output 1 if
S and T intersect, and 0 otherwise.

We will see in upcoming lectures that inner product is hard for nondeterministic, randomized
and deterministic communication complexity.

3 Randomized vs. Deterministic CC

Definition 2. For a function f : X × Y → Z, the (deterministic) communication complexity of
f , denoted by Pcc (f ), is the minimum cost of Π, over all protocols Π that compute f . Pcc (f ) is a
function of n, the length of x and y.

In the probabilistic case, players can toss random bits. There are two models depending on
whether the coin tosses are public or private. In the public random string model the players share
a common random string, while in the private model each player has his/her own private random
string. The following definitions apply to the model with private strings. For example, BPPccε (f )
denotes the randomized communication complexity of computing f with two-sided error , in the
private coin model. In the public coin model, we denote the randomized BPP communication
complexity of f by BPPcc ε
pub (f ).

Definition 3. Let Π be a randomized protocol.

Zero-sided error: Π computes a function f with zero-sided error if for every (x, y),

Pr[Π(x, y) = f (x, y)] = 1.

The cost of a zero-sided error protocol Π for f is the minimum over all inputs (x, y), of the
expected communication complexity of Π on (x, y).

One-sided error: Π computes a function f (with one sided error ε) if for every (x, y) such that
f (x, y) = 0,

Pr[Π(x, y) = 0] = 1,

and for every (x, y) such that f (x, y) = 1,

Pr[Π(x, y) = 1] ≥ 1 − ε, i

Two-sided error: Π computes a function f (with error ε) if

∀ x ∈ X, y ∈ Y, Pr [Π(x, y) = f (x, y)] ≥ 1 − ε,

3
Communication Complexity and Applications Lecture #1: Spring, 2022

Definition 4. Let f : X ×Y → {0, 1} be a function. We consider the following complexity measures

for f :

• ZPPcc (f ) is the minimum average case cost of a randomized protocol that computes f with
zero error.

• For 0 < ε < 1/2, BPPccε (f ) is the minimum worst case cost of a randomized protocol that
computes f with error ε. We define BPPcc (f ) = BPPcc
1/3 (f ).

• For 0 < ε < 1/2, RPccε (f ) is the minimum worst case cost of a randomized protocol that
computes f with one-sided error ε. We define RPcc (f ) = RPcc
1/3 (f ).

Lemma 1. (Markov) RPcc 1 cc

 (f ) ≤  ZPP (f ).

Lemma 2. BPPcc (f ) = Ω(log Pcc (f )).

Now, let’s give an example for the above two protocols for the equality function.

Example 6 (Equality Revisited). Recall that EQ(x, y) = 1 iff x = y. Let’s analyse the randomized
communication complexity in the public and private coin protocol for the function EQ:

Public Coin Let x ∈ X, y ∈ Y , X = Y = {0, 1}n be the input strings, and let r ∈ P {0, 1}n be
n
Pn computes the bit a = ( i=1 xi ri )
the public coin tosses. The protocol is the following: Alice
(mod 2) and sends it to Bob. Then Bob computes b = ( i=1 yi ri ) (mod 2). The value of the
protocol is
X n n
X
P (x, y, r) = 1 iff xi ri = yi ri (mod 2).
i=1 i=1

Note that the communication is only two bits! Now let’s analyse this protocol. If x = y,
then for all r, the protocol is correct, i.e., P (x, y, r) = 1. If x 6= y, then with probability 1/2
(over the public coin tosses) P (x, y, r) = 1, i.e., our protocol is wrong. If we repeat the above
random experiment c times independently, then the probability that our protocol is wrong on
all of the executions is 1/2c . This protocol has O(1) probabilistic communication complexity
when the error  is a consstant.

Private Coin In this setting, encode the inputs x = x0 , . . . , xn−1 and y = y0 , . . . yn−1 as the
coefficients of single variate polynomials of degree at most n − 1:

n−1
X
A(z) = xi z i ,
i=0
n−1
X
B(z) = yi z i .
i=0

Consider some field F of size q ≥ 3n. If x = y then A(z) = B(z) for all z ∈ F , but if x 6= y,
then A(z) 6= B(z) for at least 2/3 of the z ∈ F (by Schwartz-Zippel). Thus, our protocol is
as follows.

4
Communication Complexity and Applications Lecture #1: Spring, 2022

1. Alice samples a randomly chosen z ∈ F and the value A(z), and sends Bob z and A(z).
2. Bob sends 1 if and only if B(z) = A(z).

Thus Bob computes the right answer with probabilisty at least 2/3. Note that the communi-
cation is only O(logn) bits.

3.1 Newman’s Theorem

The above example gives two different randomized protocols for equality; with public coins the
protocol has constant cost, and with private coins the protocol has cost O(log n). Furthermore
it is known that the equality function requires Ω(log n) bits in the private coin model, and thus
there can be an additive O(log n) savings in the public coin model. The following theorem due
to Newman states that this gap is as large as possible, since any public coin protocol can be
transformed into a private coin protocol with a small penality in the error and a small additive
penalty in the communication complexity.

Theorem 3. Let f : {0, 1}n × {0, 1}n → {0, 1} be a function. For every δ > 0 and every  > 0,
−1
BPPcc ccpub
+δ (f ) ≤ BPP  (f ) + O(log n + log δ )

Proof. We will prove that any public coin protocol Π with error  can be transformed into another
public coin protocol, Π0 such that: (i) the communication complexity of Π0 is the same as that
of Π; (ii) Π0 uses only O(log n + log δ −1 ) random bits; and (iii) the error of Π0 is at most  + δ.
The theorem follows since Π0 can be easily converted to a private coin protocol with the desired
parameters: first Alice will privately flip that many random coins, and then send them to Bob,
and then they proceed to follow the protocol Π0 .
Let Z(x, y, r) be a random variable that is equal to 1 if Π(x, y, r) outputs an incorrect answer,
and 0 otherwise. Because Π has error , Er [Z(x, y, r)] ≤  for every x, y. Let r1 , . . . , rt be random
strings, where we will soon set t = O(n/δ 2 ), and define Πr1 ,...,rt (x, y) as follows: Alice and Bob
choose i ≤ t at random, and then run Π(x, y, ri ). We will prove that there exist strings r1 , . . . , rt
such that Ei [Z(x, y, ri )] ≤  + δ for all (x, y). For this choice of strings, the protocol Πr1 ,...,rt will
be our desired protocol, Π0 .
We use the probabilistic method to show the existence of r1 , . . . , rt . Choose r1 , . . . , rt at random,
and consider a particular Pinput pair (x, y). The probability that Ei [Z(x, y, ri )] >  + δ is exactly
the probability that 1/t ti=1 Z(x, y, ri ) >  + δ. By Chernoff inequality, since Er [Z(x, y, r)] ≤ ,
t
2
X
P rr1 ,...,rt [1/t Z(x, y, ri ) − ) > δ] ≤ 2e−2δ t .
i=1

By choosing t = O(n/δ 2 ), this is smaller than 2−2n . Thus for a random choice of r1 , . . . , rt , the
probabilty that there exists a bad (x, y) such that Ei [Z(x, y, ri )] > +δ is smaller than 22n 2−2n = 1
(by the union bound). Thus there exists r1 , . . . , rt such that for every (x, y) the error of Πr1 ,...,rt
on (x, y) is at most  + δ. It is easy to check that the number of random bits used by the protocol
Πr1 ,...,rt is log t = O(log n + log δ −1 ), and that the communication complexity of Πr1 ,...,rt is the same
as that of Π.

5
Communication Complexity and Applications Lecture #1: Spring, 2022

4 Nondeterministic/co-Nondeterministic CC
In the non-deterministic model of communication complexity, players share nondeterministic bits
z. Now a protocol is a function of x, y, z, and we say that a protocol P computes a function f if
for all x, y:

f (x, y) = 1 =⇒ ∃z P (x, y, z) = 1
f (x, y) = 0 =⇒ ∀z P (x, y, z) = 0.

The communication complexity in this model is defined as the maximum length of z plus the
number of bits exchanged over all x, y. Similarly, exchanging the position of the existential and
for all quantifier we can define co-nondeterministic CC. The basic example is set disjointness (see
Example 3). If the players share log n nondeterministic bits, they guess i and check if xi = yi = 1.
Define NPcc (f ) to be the nondeterministic communication complexity of f , and similarly, let
coNPcc (f ) denote the co-nondeterministic communication complexity of f .

5 Communication Complexity Classes

To summarize, we define the following measures of communication complexity for a two-player
function f .

Definition 5. Let f be a two-player function.

1. Pcc (f ) is the deterministic communication complexity of f .

2. RPcc (f ) is the randomized one-sided communication complexity of f with error 1/3

3. BPPcc (f ) is the randomized two-sided communication complexity of f with error 1/3.

4. NPcc (f ) is the nondeterministic communication complexity for f

5. PPcc (f ) is the randomized communication complexity of f with unbounded error. That is, on
all instances, the protocol is correct with probability greater than 1/2.

6. ZPPcc (f ) is the randomized zero-error communication complexity of f .

We have the following easy relationships:

Pcc (f ) ≥ RPcc (f ) ≥ BPPcc (f ).

We also have
Pcc (f ) ≥ RPcc (f ) ≥ NPcc (f ).
Remark: Unlike the analagous classical complexity classes where the above relationships are not
know to be proper, in the communication complexity world, all of the above inequalities are prov-
ably proper. (That is, for each inequality C1 ≥ C1 , there exists a function f such that C1 (f ) is
exponentially larger than C2 (f ).)

6
Communication Complexity and Applications Lecture #1: Spring, 2022

6 Applications
Communication complexity arguments have found numerous application to a large number of dif-
ferent areas. Applications include the following.

1. Bisection width of networks

2. VLSI

3. Data structures – cell probe model and dynamic data structures

4. Boolean circuit complexity, branching program complexity

5. Quantum complexity

6. Extension Complexity of linear programming and semi-definite programming.

7. Turing machine time-space trade-offs

8. Streaming algorithms

9. Game theory (truthfulness vs. accuracy, mechanism design)

10. Differential privacy

11. Property Testing

12. Differential Privacy

13. Learning Theory

14. Proof complexity

15. Graph Theory (Alon-Seymour Conjecture)