Prof. Mark Bun
CAS CS 591 B: Communication Complexity
Lecture Notes 11:
Direct Sum
Fall 2019
Reading.
• Rao-Yehudayo Chapter 7
Does solving k instances of a given computational task require more resources than are required to solve a single task? Direct sum theorems (as well as related direct product theorems and XOR lemmas) address this question. The direct sum question is one of the most basic questions one can ask in any computational model and here we’ll see some answers to it in communication and information complexity.
Foracommunicationproblemf:X×Y →{0,1},letfk :Xk×Yk →{0,1}k bethefunction fk(x1, . . . , xk, y1, . . . , yk) = (f(x1, y1), . . . , f(xk, yk)). A randomized protocol computes fk to error εifforall(x,y)∈Xk×Yk wehavePr[Π(x,y)=fk(x,y)]≥1−ε. Notethatifwehaveaprotocol computing f to error ε with communication cost c, then we can compute f k to error (1 − ε)k with communication cost k · c.
•
•
•
1
Information cost behaves elegantly with respect to k-fold composition.
Theorem 1. Let f be any communication problem and let μ be a distribution over the domain of f. Then for every ε > 0,
ICε (fk) = k · ICε(f).
Note that naïve repetition of a protocol for f both increases the communication cost by a factor of k and decreases the success probability exponentially in k. (Strong) direct product theorems identify situations where both an increase in communication and exponential decrease in success probability are necessary. For instance, a direct product theorem might show that if c is the communication cost of computing f to error 1/3, then computing fk to error 2−Ω(k) requires communication Ω(k · c).
Related to direct product theorems are XOR lemmas which address the task of computing the boolean function XOR(f(x1,y1),…,f(xk,yk)). Intuitively, successfully computing the XOR of k copies of f should necessitate computing every copy simultaneously. An XOR lemma might say that computing XORk ◦ f to error 1/2 + 2−Ω(k) requires communication Ω(k · c).
Direct sum theorems are weaker than direct product theorems, and ask whether computing fk requires more resources than computing f itself for some xed success probability ε. A direct sum theorem may say that computing f k to error 1/3 requires communication Ω(k · c).
Additivity of Information Cost
μ,k
μ
1
Here, the notation ICε (fk) refers to the least information cost of a protocol computing fk μ,k
which has success probability 1 − ε on each individual copy.
Proof. Fix ε > 0. The direction ICμ,k(fk) ≤ k · ICμ(f) is obvious since we can just run a protocol Π computing f on each copy independently. For the other direction, let Π be a protocol computing fk. We will use it to construct a protocol Π′ computing f with information cost ICμ,k(Π)/k. The protocol is as follows. On inputs (x,y), Alice and Bob use public randomness to sample an index i∗ ∈ [n] and set ai∗ = x and bi∗ = y. They also publicly sample a1,…,ai∗−1 ∼ μx and bi∗+1,…,bn ∼ μy i.i.d. Then for i > i∗, Alice privately samples ai ∼ μx|y = bi and for i < i∗, Bob privately samples bi ∼ μy|y = ai. The parties then execute the protocol Π(a,b) and output the value computed in the i∗-th coordinate.
We now argue that Π′ has low internal information cost. We calculate
I(y; Π′|x) ≤ I(y; Π′, a|x)
= I(y;Π,i∗,a,bi∗+1,...,bn|x)
= I(y; i∗, a, bi∗+1, . . . , bn|x) + I(y; Π|i∗, a, bi∗+1, . . . , bn) = I(y;Π|i∗,a,bi∗+1,...,bn)
1 k
= k
1 k
I(bi∗;Π|a,bi+1,...,bn,i = i∗) I(bi;Π|a,bi+1,...,bn)
i=1
= k
= 1I(b;Π|a)
i=1 k
by the chain rule.
2 Direct Sum for Randomized Communication
Theorem 2. If BPPcc(f) = c, then BPPcc(fk) ≥ Ω(c√k/ log c).
To prove this theorem, we need a dierent compression result due to Braverman, Barak, Chen,
and Rao:
Theorem 3. A protocol with communication cost c and information cost I can be compressed to a
protocol with communication cost
√
O( Ic log(c/ε)/ε)
with error ε.
Proof of Theorem 2. By Yao's principle, there is a distribution μ such that D1/3(f) ≥ c. Suppose
μ
Π is a protocol computing fk with success probability 3/4 and length l. Then there exists a xing of the randomness r in Π such that Πr computes fk with success probability 3/4 over inputs drawn from μ⊗k. Now let Π′ be the protocol used in the proof of Theorem 1. Then Π′ computes f over μ
with success probability at least 3/4 and has internal information cost ICμ(Π′)= 1ICμ⊗k(Πr)≤ l.
kk
2
Compressing Π′ according to Theorem 5 gives a protocol Π′′ with communication l √
O k·l·logl =O(llogl/ k) √√
and error less than 1/3. Hence llogl/ k ≥ Ω(c), so l ≥ Ω(c k/logc). 3 Information Equals Amortized Communication
Theorem 4. For every ε > 0,
ICε(f)=lim1·Dε (fk) μ k→∞ k μ,k
where Dε (fk) denotes the least cost of a deterministic protocol computing fk over μ⊗k with success μ,k
probability at least 1 − ε on every copy.
To prove this theorem, we recall Braverman and Rao’s compression for interactive protocols:
Theorem 5. Let Π be a private coin protocol with r rounds and internal information cost I. Then there is a public coin protocol τ such that with probability at least 1 − ε,
• τ (x, y) (can be used to reconstruct a transcript which) has the same distribution as Π(x, y) for every x, y and
√
• The expected communication of τ is I + O(r log(r/ε) + Proof sketch. From Theorem 1 we have
Ir).
1·Dε (fk)≥1·ICε⊗k(fk)=ICε(f). kμ,kkμ μ
We now prove the other direction. Let δ > 0 and let Π be a protocol computing f to error ε − δ in r rounds. Let Πk denote this protocol applied to k copies of f independently. Note that the number of rounds of Πk is still r (since we can batch calls to Π together) and that
ICμ⊗k (Πk) = k · ICμ(Π).
Now we compress Πk to another protocol Π′ which uses expected communication
k·ICμ(Π)+O(rlog(r/δ))+ k·r·ICμ(Π)
and additional error δ. Moreover, the communication cost of Π′ concentrates around its expectation, so we can obtain a similar bound on its worst case communication. Sending k → ∞ and δ → 0 gives the result.
3