Prof. Mark Bun
CAS CS 591 B: Communication Complexity
Lecture Notes 3:
Randomized Communication, Newman’s Theorem
Fall 2019
Reading.
• Rao-Yehudayoff Chapter 3, through pg. 71 + “Public Coins vs. Private Coins”
We’ll begin our systematic study of randomized protocols, or protocols which are allowed to toss coins to make random choices. We will see that some functions can be computed much more efficiently with randomness, but also see lower bound techniques which will show that other functions remain hard.
Concentration inequalities will be used frequently throughout this lecture, so let’s state Hoeffd- ing’s inequality (or an “additive Chernoff bound”’) which will suffice for our purposes.
Theorem 1 (Hoeffding’s Inequality). Let Z1, . . . , Zk ∈ [0, 1] be independent random variables, and let Z = 1 n Zi. Then for every α>0, we have
Pr[Z − E[Z] > α] ≤ e−2α2k.
k i=1
Example 2. Let’s design a protocol for estimating the fractional Hamming distance between two bit strings. Alice and Bob hold x, y ∈ {0, 1}n and their goal is to determine ∆ = |x − y|/n up to small additive error α. One strategy they can use is random sampling. Using shared randomness, Alice and Bob sample indices i1, . . . , ik i.i.d. from [n] and compute the empirical fraction
ˆ 1k
jjk
inequality,
Pr[|∆ˆ − ∆| > α] ≤ 2 exp(−2α2k).
So to get this probability below, say, 1/3 it suffices to take k = Ω(1/α2). In particular, this means
we can estimate ∆ to within constant error using constant communication, and to within o( n) error using o(n) communication.
On the other hand, deterministically, even estimating ∆ to within constant error α < 1/4 requires Ω(n) communication. To see this, let E : {0,1}n → {0,1}m be an error correcting code with relative distance 0 < δ < 1/2, meaning x ̸= y ∈ {0, 1}n implies |E(x) − E(y)|/n > δ. Such codes exist with m = Oδ(1). Suppose we could deterministically estimate the Hamming distance between m-bit strings to within relative error δ/2 using communication c. Then Alice and Bob could compute EQn with communication c + 2 by encoding their inputs, estimating the distance between their encodings, and accepting iff this estimate is ≤ δ/2. Hence c = Ω(n) = Ωδ(m).
1
|xij −yij|.
{0,1} by Zj = 1 if xi ̸= yi . Then ∆ˆ = 1(Z1 +···+Zk) and E[∆ˆ] = E[Zj] = ∆. By Hoeffding’s
∆=k
We now analyze the approximation guarantees of this protocol. Define random variables Z1, . . . , Zk ∈
j=1
√
Example 3. In the first lecture, we saw a randomized protocol for computing EQn to error 2−k using kn bits of public randomness. We can also design a protocol using private randomness. Alice selects a prime p at random among the first n2 primes. Interpreting her input x as an n-bit number, she sends both p and x mod p to Bob using O(log n) bits of communication. Bob then checks whether x mod p = y mod p.
If x = y, the protocol always succeeds. Otherwise, suppose x ̸= y. Since |x − y| ≤ 2n, it has at most n distinct prime factors. So the protocol succeeds with probability at least 1 − 1/n.
1 Private Coin Protocols
We’ll begin by modeling private coin protocols. In a randomized protocol with private coins, Alice and Bob each sample independent bit strings rA and rB uniformly at random. (Usually the length of these strings will not be an important parameter for us, but one can also study tradeoffs between randomness and communication). These strings can be taken as additional parameters in their next message functions mv, i.e., if a vertex in the protocol tree belongs to Alice, we can think of her next message as mv(x;rA). Note that every fixing of the strings rA and rB gives nothing more than a deterministic protocol.
Definition 4. A private-coin randomized protocol Π computes a function f : X × Y → {0, 1} with two-sided error ε if for every (x, y) ∈ X × Y ,
Pr [Π(x,y;rA,rB)=f(x,y)]≥1−ε. rA ,rB
The BPPpriv cost of such a protocol is the maximum depth of any of the induced deterministic ε
protocols Π(·,·;r ,r ), and BPPpriv(f) is the least cost of any private coin protocol computing f ABε
to error ε.
As we’ve done before, we may also define the class BPPcc to consist of the sequences of functions
{fn : {0, 1}n × {0, 1}n → {0, 1}} for which BPPpriv(fn) = polylog(n). The rest of this lecture is 1/3
devoted to understanding how robust this definition is. First, does the choice of the constant 1/3 matter? Second, does it matter that we are looking at private coin protocols? Or can public coins make a difference?
2 Error Reduction
Theorem5.Let0<ε,δ<1/2.ThenBPPpriv(f)≤O(log(1/ε)/δ2)·BPPpriv (f). ε 1/2−δ
Proof. Suppose Π is a private-coin randomized protocol with error 1 − δ. Let Πk be the protocol 2
obtained by running Π k times using independent coin tosses and taking the majority vote of the outcomes. Let us analyze the error of Πk.
Fixaninput(x,y)∈X×Y. Fori=1,...,k,letZi ∈{0,1}beanindicatorrandomvariablefor the event that the ith run of Π makes an error in computing f (over the random choices of rA,rB).
Then E[Zi] ≤ 1 −δ. Note that an error of Πk corresponds to the event Z = 1 k
2 k i=1
by Hoeffding’s inequality, the error probability of Πk is
Pr[Z ≥ 1/2] ≤ Pr [Z − E[Z] ≥ δ] ≤ e2δ2k
which is at most ε by taking k = log(1/ε)/2δ2.
2
Zi ≥ 1/2. So
Can the error in a randomized protocol be completely removed? A different argument shows that this is possible with at most an exponential blowup in communication.
Theorem 6. Let 0 < δ < 1/2, and let c = BPPpriv (f). Then Pcc(f) ≤ 2c · (log(1/δ) + c). In 1/2−δ
particular, BPPpriv(f) ≥ Ω(log Pcc(f)). 1/3
Proof. Let Π be a randomized protocol tree of depth c. We will show how to simulate the execution of this tree using roughly 2c bits of communication. For a fixed input (x, y), let pl be the probability of the parties reaching leaf l during a random execution of the protocol. If the parties could compute all of the pl’s, then they could simply accept iff the probability of reaching a 1 leaf is higher than the probability of reaching a 0 leaf.
Note that since Alice and Bob use independent coin tosses, we can decompose pl = pAl ·pBl , where pAl is the probability over Alice’s coin tosses that her messages are consistent with those needed to reach leaf l, and similarly for Bob. Alice can then send all 2c probabilities pAl . The problem is that each probability is a real number which may require many bits to send.
Alice can get around this by approximating each pAl to a precision of k = log(1/δ) + c bits. This A A A −k −c
guarantees that every estimate pˆl satisfies |pl − pˆl | < 2 = 2 δ. Hence the total error over all the leaves is smaller than δ, which means that the weighted majority of the leaves still gives the correct answer.
Example 7. The private coin protocol we saw for Equality is optimal, since BPPpriv(EQn) ≥ 1/3
Ω(log Pcc(EQn)) ≥ Ω(log n). Since Equality has a constant communication public coin protocol, this implies that there can be arbitrarily large gaps between public and private coin communication costs.
3 Newman’s Theorem
In the public coin model, Alice and Bob are both given access to a shared random string r. Public coin protocols are, of course, more powerful than private coin protocols since Alice and Bob could simply partition r into rA,rB to simulate a private coin protocol. Moreover, there is a strict separation. Private coin protocols for Equality require Ω(logn) communication, but we saw a public coin protocol with O(1) communication. How much more powerful can public coin protocols be?
It turns out that the answer is “not so much.” The following theorem, due to Ilan Newman, shows that any public coin protocol can be simulated by a private coin protocol with a small penalty in the error and a small additive penalty in communication.
Theorem 8. Let f : {0,1}n × {0,1}n → {0,1}. For every ε,δ > 0, we have BPPpriv(f) ≤ ε+δ
BPPpub(f) + O(log n + log(1/δ)). ε
Proof. Suppose we have a public coin protocol Π that achieves error ε using a public random string r. We will compile this protocol into a private coin protocol with similar error and communication. The protocol will be based on the following Lemma:
Lemma 9. For some t = O(n/δ2) there exist strings r1, . . . , rt such that, for every (x, y) ∈ {0, 1}n × {0, 1}n, we have
Pr [Π(x,y;ri)̸=f(x,y)]≤ε+δ. i←[t]
3
Assuming the Lemma, let’s see how to design a good protocol. Hardcode the set of strings r1,…,rt into the design of our new protocol. Alice samples (using private randomness) an index i ∈ [t] and sends it to Bob using O(log n) + O(log(1/δ)) bits. The parties then simulate the protocol Π as if the public random string were ri. The Lemma shows that this succeeds with error at most ε + δ, and incurs communication overhead O(log n) + O(log(1/δ)) over Π itself.
Let us now see how to prove the Lemma.
Proof of Lemma 9. We construct the set of strings r1, . . . , rt using the probabilistic method. That is, we show that a random choice of r1,…,rt satisfy the conditions of the Lemma with positive probability.
For a pair of inputs (x, y) and a randomness string r, let Z(x, y, r) = 1 if Π(x, y; r) ̸= f(x, y) and Z(x,y,r) = 0 otherwise. We can rephrase the Lemma as asserting that the set of strings r1,…,rt
satisfies
1 t
Z(x, y, ri) ≤ ε + δ
for every pair (x,y). Pick a sequence r1,…,rt independently at random, and fix a pair of inputs
t
(x, y). Then E[Z(x, y, ri)] ≤ ε, so by Hoeffding’s inequality,
r1,…,rt t i=1
For t = O(n/δ2), this probability is smaller than 2−2n. By union bounding over all pairs (x, y), we
i=1
t
Pr 1Z(x,y,ri)>ε+δ ≤e−2δ2t.
have
1t
Pr ∃(x,y)∈{0,1}n ×{0,1}n : Z(x,y,ri)>ε+δ <1,
r1,...,rt t i=1 and hence some good set of strings r1, . . . , rt exists.
Newman’s Theorem allows us to focus our study to public coin protocols, which can be convenient for several reasons. We’ve already seen a few examples of how it can be easier to design public coin protocols. Another nice feature of public coin protocols is that they can be thought of as arbitrary distributions over deterministic protocols. (I.e., Alice and Bob use public randomness to jointly sample a protocol from a collection of deterministic protocols, and execute it over their inputs.) We’ll see in the next lecture how this perspective is useful for proving lower bounds.
4