Lecture 11.Information theoretical argument An interesting technique to prove lower bound is to use some information theoretical argument.Since introduced by [CSWY01],information complexity has been studied and applied to prove strong lower bounds of communication complexity.In this lecture,we will first introduce/review some basic notions such as entropy and mutual information,and then show how to use them to prove a linear lower bound for randomized communication complexity of Disjointness function [BYJKS04],one of the most important functions in communication complexity 1.Review of basic notions in information theory Let's first review some basic concepts in information theory.All these can be found in the standard textbook such as [CT06](Chapter 1).Suppose that X is a discrete random variable with alphabet Xand probability mass function p(x)=Pr [X =x].Following the standard notation in information theory,we sometimes also use the capital letter X to denote the distribution.By writing xX,we mean to draw a sample x from the distribution X.The entropy H(X)of a discrete random variable X is defined by H(W=∑p(x)log2p). XEX (Here we use the convention that 0 log20=0.)One intuition is that entropy measures the amount of the uncertainty of a random variable.The more entropy X has,the more uncertain it is.In particular,if H(X)=0 then X is fixed/deterministic.The maximum entropy for any random variable on X is log2X: 0≤H(X)≤log2lq, with upper bound achieved by the uniform distribution. Sometimes we have more than one random variable.If (X,Y)is a pair of random variables on Xx y,distributed according to a joint distribution p(x,y),then the total entropy is simple:
Lecture 11. Information theoretical argument An interesting technique to prove lower bound is to use some information theoretical argument. Since introduced by [CSWY01], information complexity has been studied and applied to prove strong lower bounds of communication complexity. In this lecture, we will first introduce/review some basic notions such as entropy and mutual information, and then show how to use them to prove a linear lower bound for randomized communication complexity of Disjointness function [BYJKS04], one of the most important functions in communication complexity. 1. Review of basic notions in information theory Let’s first review some basic concepts in information theory. All these can be found in the standard textbook such as [CT06] (Chapter 1). Suppose that 𝑋 is a discrete random variable with alphabet X and probability mass function 𝑝(𝑥) = Pr [𝑋 = 𝑥]. Following the standard notation in information theory, we sometimes also use the capital letter 𝑋 to denote the distribution. By writing 𝑥 ← 𝑋, we mean to draw a sample 𝑥 from the distribution 𝑋. The entropy 𝐻(𝑋) of a discrete random variable 𝑋 is defined by 𝐻(𝑋) = ∑ 𝑝(𝑥) log2 𝑝(𝑥) 𝑥∈X . (Here we use the convention that 0 log2 0 = 0.) One intuition is that entropy measures the amount of the uncertainty of a random variable. The more entropy 𝑋 has, the more uncertain it is. In particular, if 𝐻(𝑋) = 0 then 𝑋 is fixed/deterministic. The maximum entropy for any random variable on X is log2 |X|: 0 ≤ 𝐻(𝑋) ≤ log2 |X|, with upper bound achieved by the uniform distribution. Sometimes we have more than one random variable. If (𝑋, 𝑌) is a pair of random variables on X × Y, distributed according to a joint distribution 𝑝(𝑥, 𝑦), then the total entropy is simple:
H(X,Y)= >p(x.y)logzp(x.y). xeXy∈y We can also define the conditional entropy H(YIX)=Ex-x[H(YX =x)],namely the expected entropy of the conditional distribution YX =x.Thus,H(YX)>0.Another basic fact is the chain rule: H(X,Y)=H(X)+H(YX). The chain rule also works with conditional entropy: H(X,YZ)=HZ)+H(Y X,Z). And if we have more variables,it also works: H(X1,...,XnZ)=H(XIZ)+H(X2IX1,Z)++H(XnlX1,...Xn-1,Z) ≤H(X1lZ)+H(X2lZ)+…+H(XnlZ) where the inequality is usually referred to as the subadditivity of entropy.The relative entropy of two distributions p and q is Dpl)=∑p(x)l1og p(x) q(x) For a joint distribution (X,Y)=p(x,y),the mutual information between X and Y is I(X;Y)=D(p(x,y)Ilp(x)p(y))=H(X)-H(XIY). It is a good exercise to verify that the above equality holds.But the latter one has a clear explanation:the mutual information is the amount of uncertainty of X minus that when Y is known.In this way,it measures how much Y contains the information of X.It is not hard to verify that it's symmetric:I(X;Y)=H(X)-H(Y)=H(Y)-H(Y X),and that it's nonnegative: I(X,Y)≥0.That is,.I(X,Y)≤min{H(X),H(Y)} The conditional mutual information is defined by I(X,Y D)=Ed[IX,YID d)] It is not hard to see that
𝐻(𝑋, 𝑌) = ∑ 𝑝(𝑥,𝑦) log2 𝑝(𝑥, 𝑦) 𝑥∈X,𝑦 ∈Y . We can also define the conditional entropy 𝐻(𝑌|𝑋) = 𝐸𝑥←𝑋 [𝐻(𝑌|𝑋 = 𝑥)], namely the expected entropy of the conditional distribution 𝑌|𝑋 = 𝑥. Thus, 𝐻(𝑌|𝑋) ≥ 0. Another basic fact is the chain rule: 𝐻(𝑋, 𝑌) = 𝐻(𝑋) + 𝐻(𝑌|𝑋). The chain rule also works with conditional entropy: 𝐻(𝑋, 𝑌|𝑍) = 𝐻(𝑋|𝑍) + 𝐻(𝑌|𝑋, 𝑍). And if we have more variables, it also works: 𝐻(𝑋1 ,… , 𝑋𝑛 |𝑍) = 𝐻(𝑋1 |𝑍) + 𝐻(𝑋2 |𝑋1 ,𝑍) + ⋯ + 𝐻(𝑋𝑛 |𝑋1 , …𝑋𝑛−1 , 𝑍) ≤ 𝐻(𝑋1 |𝑍) + 𝐻(𝑋2 |𝑍) + ⋯ + 𝐻(𝑋𝑛 |𝑍), where the inequality is usually referred to as the subadditivity of entropy. The relative entropy of two distributions 𝑝 and 𝑞 is 𝐷(𝑝||𝑞) = ∑ 𝑝(𝑥) log2 𝑝(𝑥) 𝑞(𝑥) 𝑥∈X . For a joint distribution (𝑋, 𝑌) = 𝑝(𝑥, 𝑦), the mutual information between 𝑋 and 𝑌 is 𝐼(𝑋; 𝑌) = 𝐷(𝑝(𝑥,𝑦)||𝑝(𝑥)𝑝(𝑦)) = 𝐻(𝑋) − 𝐻(𝑋|𝑌). It is a good exercise to verify that the above equality holds. But the latter one has a clear explanation: the mutual information is the amount of uncertainty of 𝑋 minus that when 𝑌 is known. In this way, it measures how much 𝑌 contains the information of 𝑋. It is not hard to verify that it’s symmetric: 𝐼(𝑋;𝑌) = 𝐻(𝑋) − 𝐻(𝑋|𝑌) = 𝐻(𝑌) − 𝐻(𝑌|𝑋), and that it’s nonnegative: 𝐼(𝑋, 𝑌) ≥ 0. That is, 𝐼(𝑋, 𝑌) ≤ min{𝐻(𝑋), 𝐻(𝑌)} The conditional mutual information is defined by 𝐼(𝑋, 𝑌|𝐷) = 𝐸𝑑 [𝐼(𝑋, 𝑌|𝐷 = 𝑑)] It is not hard to see that
I(X,YID)≤min{H(XID),H(YID)}≤log2lI and I(X;Y D)=H(X D)-H(X YD). Lemma 1.1.If X=X1...Xn,Y =Y1...Yn,and D =D1...Dn:and (Xi,Yi,Di)'s are independent,then I(XYID)≥ Proof.I(X;YID)=H(XID)-H(XIYD) =∑H(X:ID)-H(XIYD) ∥H(XID)=∑iH(XlD):independence of(X,D)'s ≥iH(XlD)-∑iH(XlYD)∥H(XIYD)≤∑iH(XlYD):subadditivity of entropy =∑=1I(XiYID) 2.Linear lower bound for the Disjointness function The information complexity is an approach to prove lower bounds for communication complexity.The basic idea is that for some functions,any small-error protocol has to contain enough information about the input.Thus the communication cost,namely the length of the protocol,is also large. Now we focus on Disjointness function,where both Alice and Bob have input set {0,1)"and f(x,y)=1 iff i[n],=yi=1.We sometimes use subscript -i to denote the set [n]-i).Denote by Re(f)the s-error private-coin communication complexity of f.We want to prove the following. Theorem 2.1.Re(f)=(n). First,we define a distribution on inputs.Again,we'll use capital letters (X,Y)to denote both the random variables and the distribution.We also introduce a third random variable D with the sample space (0,1)".The joint distribution (X,Y,D)is defined by u",where
𝐼(𝑋, 𝑌|𝐷) ≤ min{𝐻(𝑋|𝐷), 𝐻(𝑌|𝐷)} ≤ log2 |X| and 𝐼(𝑋; 𝑌|𝐷) = 𝐻(𝑋|𝐷) − 𝐻(𝑋|𝑌𝐷). Lemma 1.1. If 𝑋 = 𝑋1 …𝑋𝑛 , 𝑌 = 𝑌1 …𝑌𝑛 , and 𝐷 = 𝐷1 … 𝐷𝑛 , and (𝑋𝑖 ,𝑌𝑖 ,𝐷𝑖 )’s are independent, then 𝐼(𝑋; 𝑌|𝐷) ≥ ∑𝐼(𝑋𝑖 ;𝑌|𝐷) 𝑛 𝑖=1 Proof. 𝐼(𝑋; 𝑌|𝐷) = 𝐻(𝑋|𝐷) − 𝐻(𝑋|𝑌𝐷) = ∑ 𝐻(𝑋𝑖 |𝐷) 𝑖 − 𝐻(𝑋|𝑌𝐷) // 𝐻(𝑋|𝐷) = ∑ 𝐻(𝑋𝑖 |𝐷) 𝑖 : independence of (𝑋𝑖 ,𝐷𝑖 )’s ≥ ∑ 𝐻(𝑋𝑖 |𝐷) 𝑖 − ∑ 𝐻(𝑋𝑖 |𝑌𝐷) 𝑖 // 𝐻(𝑋|𝑌𝐷) ≤ ∑ 𝐻(𝑋𝑖 |𝑌𝐷) 𝑖 : subadditivity of entropy = ∑ 𝐼(𝑋𝑖 ;𝑌|𝐷) 𝑛 𝑖=1 □ 2. Linear lower bound for the Disjointness function The information complexity is an approach to prove lower bounds for communication complexity. The basic idea is that for some functions, any small-error protocol has to contain enough information about the input. Thus the communication cost, namely the length of the protocol, is also large. Now we focus on Disjointness function, where both Alice and Bob have input set {0,1} 𝑛 and 𝑓(𝑥, 𝑦) = 1 iff ∃𝑖 ∈ [𝑛], 𝑥𝑖 = 𝑦𝑖 = 1. We sometimes use subscript – 𝑖 to denote the set [𝑛] − {𝑖}. Denote by 𝑅𝜖 (𝑓) the 𝜀-error private-coin communication complexity of 𝑓. We want to prove the following. Theorem 2.1. 𝑅𝜖 (𝑓) = Ω(𝑛). First, we define a distribution on inputs. Again, we’ll use capital letters (𝑋, 𝑌) to denote both the random variables and the distribution. We also introduce a third random variable 𝐷 with the sample space {0,1} 𝑛 . The joint distribution (𝑋, 𝑌,𝐷) is defined by 𝜇 𝑛 , where
u(xiy,di)=(000,010,001,101)each with probability 1/4.That is,(Xi,Yi,D)'s are independent for different i's,and each (Xi,Yi,Di)is distributed according to u. Now take a private-coin protocol with minimum worst-case communication cost among all protocols that have g-error in the worst case.Consider the messages over all rounds,namely the entire transcript of the conversation.Denote it by I,and its length(i.e.the number of bits) by II.Note that since the input (X,Y)is a random variable,and the protocol is randomized, the induced transcript I is also a random variable.By the relation among mutual information,entropy and the size of sample space,we have Re(Disn)=lrl≥H(TlD)≥I(T;XYID). Note that both X and Y can be decomposed into n bits:X=X1...Xn and Y=Y1...Y Each Xi and Yi are also random variables,and note that (Xi,Yi,Di)for different iare independent.Thus we can apply Lemma 1.1 and have 1r;XY1D)≥∑10：xXID). Since I(r;XiYiID)=Ea_[I(T;XiYiIDi,D-i=d_i)].we have n 1,xYID)≥∑Ea,luC;xYID.D-=d,l i=1 For each fixed d_i(0,1)-1,we design a worst-case s-error private-coin protocol (d_), for the function g()=xiAy,as follows.Note that the protocol should work for all possible inputs (xiy),not only those in the support of (Xi,Y). i(d_i):On input (xiyi), 1.Generate (X'i,Y')from um-1D_i=d_i. 2.Run protocol I on (xiX'_i,yiY'_)and output the answer. Lemma 2.2. 1.Ti(d_i)is private-coin
𝜇(𝑥𝑖 ,𝑦𝑖 , 𝑑𝑖 ) = (000, 010,001, 101) each with probability 1/4. That is, (𝑋𝑖 ,𝑌𝑖 ,𝐷𝑖 )’s are independent for different 𝑖’s, and each (𝑋𝑖 , 𝑌𝑖 ,𝐷𝑖 ) is distributed according to 𝜇. Now take a private-coin protocol with minimum worst-case communication cost among all protocols that have 𝜀-error in the worst case. Consider the messages over all rounds, namely the entire transcript of the conversation. Denote it by 𝛤, and its length (i.e. the number of bits) by |𝛤|. Note that since the input (𝑋, 𝑌) is a random variable, and the protocol is randomized, the induced transcript 𝛤 is also a random variable. By the relation among mutual information, entropy and the size of sample space, we have 𝑅𝜖 (𝐷𝑖𝑠𝑗𝑛 ) = |𝛤| ≥ 𝐻(𝛤|𝐷) ≥ 𝐼(𝛤;𝑋𝑌|𝐷). Note that both 𝑋 and 𝑌 can be decomposed into n bits: 𝑋 = 𝑋1 … 𝑋𝑛 and 𝑌 = 𝑌1 … 𝑌𝑛 . Each 𝑋𝑖 and 𝑌𝑖 are also random variables, and note that (𝑋𝑖 , 𝑌𝑖 ,𝐷𝑖 ) for different i are independent. Thus we can apply Lemma 1.1 and have 𝐼(𝛤; 𝑋𝑌|𝐷) ≥ ∑𝐼(𝛤; 𝑋𝑖𝑌𝑖 |𝐷) 𝑛 𝑖=1 . Since 𝐼(𝛤; 𝑋𝑖𝑌𝑖 |𝐷) = 𝐄𝑑−𝑖 [𝐼(𝛤; 𝑋𝑖𝑌𝑖 |𝐷𝑖 ,𝐷−𝑖 = 𝑑−𝑖 )], we have 𝐼(𝛤; 𝑋𝑌|𝐷) ≥ ∑𝐄𝑑−𝑖 [𝐼(𝛤; 𝑋𝑖𝑌𝑖 |𝐷𝑖 ,𝐷−𝑖 = 𝑑−𝑖 )] 𝑛 𝑖=1 . For each fixed 𝑑−𝑖 ∈ {0,1} 𝑛−1 , we design a worst-case ε-error private-coin protocol 𝛤𝑖 (𝑑−𝑖 ), for the function 𝑔(𝑥𝑖 ,𝑦𝑖 ) = 𝑥𝑖 ∧ 𝑦𝑖 , as follows. Note that the protocol should work for all possible inputs (𝑥𝑖 ,𝑦𝑖 ), not only those in the support of (𝑋𝑖 ,𝑌𝑖 ). 𝛤𝑖 (𝑑−𝑖 ): On input (𝑥𝑖 ,𝑦𝑖 ), 1. Generate (𝑋’−𝑖 , 𝑌’−𝑖 ) from 𝜇 𝑛−1 |𝐷−𝑖 = 𝑑−𝑖 . 2. Run protocol 𝛤 on (𝑥𝑖𝑋’−𝑖 , 𝑦𝑖𝑌’−𝑖 ) and output the answer. Lemma 2.2. 1. 𝛤𝑖 (𝑑−𝑖 ) is private-coin
2.(d_)has g-error in the worst case. 3.I(r;XiYlDi,D_i=d_i)=I(n(d_i);XiYilDi). Proof. 1.Note that once d_i is fixed,then each (Xj,Y)(E [n]-i)is a product distribution (over Alice and Bob's spaces).Indeed,if d=0,then (Y)xU where U is the uniform distribution on {0,1).If di =1,then (Xj,Y)~U x 0. 2. Since u only puts weight on 0-inputs,Disjn(xY)=xiAyi,and thus i(di)is correct on (xi,yi)iff r is correct on (xiX'_i,yiY_).Thus the error probability of Ii(d)on (xiy)is the average (over X'i and Y)error prob ofr on (xY).Since I has error probability at most s on all inputs,so is (d-) on all its possible inputs (xiyi). 3.does nothing but invoking I on the same input distribution u". Now we have 1r;xY1D)≥∑.Ea,l(d)xYID Next we show that any worst-case &-error private-coin protocol for g has to contain a constant amount of information about (Xi,Y)(conditioned on Di). Lemma 2.3.For any worst-case s-error private-coin protocol for g with transcript I7, I(Π；X;YlD)=n(1) Proof.Denote the transcript for input (a,b)by Iab.First,we show that if the protocol doesn't contain enough information,then oo is close to both o and 10 Thus o is close to I10 Consider the Hellinger distance: nmq2=1-∑pa=2∑何-2 We have I(n;XiYiD )=I(n;XiYiID =0)+I(n;XiYiD=1) ≥3h(lo,几1)2+2h(no,几1o)2∥ForB~U,1(B,PB)≥h(po,P1)2 ≥2h(1o,o1)2 /Cauchy-Schwartz and Triangle
2. 𝛤𝑖 (𝑑−𝑖 ) has 𝜀-error in the worst case. 3. 𝐼(𝛤;𝑋𝑖𝑌𝑖 |𝐷𝑖 ,𝐷−𝑖 = 𝑑−𝑖 ) = 𝐼(𝛤𝑖 (𝑑−𝑖 );𝑋𝑖𝑌𝑖 |𝐷𝑖 ). Proof. 1. Note that once 𝑑−𝑖 is fixed, then each (𝑋𝑗 ,𝑌𝑗 ) (𝑗 ∈ [𝑛] − 𝑖) is a product distribution (over Alice and Bob’s spaces). Indeed, if 𝑑𝑗 = 0, then (𝑋𝑗 ,𝑌𝑗 ) ∼ 0 × 𝑈 where 𝑈 is the uniform distribution on {0,1}. If 𝑑𝑗 = 1, then (𝑋𝑗 ,𝑌𝑗 ) ∼ 𝑈 × 0. 2. Since 𝜇 only puts weight on 0-inputs, 𝐷𝑖𝑠𝑗𝑛 (𝑥𝑖𝑋’−𝑖 ,𝑦𝑖𝑌’−𝑖 ) = 𝑥𝑖 ∧ 𝑦𝑖 , and thus 𝛤𝑖 (𝑑−𝑖 ) is correct on (𝑥𝑖 ,𝑦𝑖 ) iff 𝛤 is correct on (𝑥𝑖𝑋’−𝑖 ,𝑦𝑖𝑌’−𝑖 ). Thus the error probability of 𝛤𝑖 (𝑑−𝑖 ) on (𝑥𝑖 ,𝑦𝑖 ) is the average (over 𝑋’−𝑖 and 𝑌’−𝑖 ) error prob of Γ on (𝑥𝑖𝑋’−𝑖 ,𝑦𝑖𝑌’−𝑖 ). Since Γ has error probability at most 𝜀 on all inputs, so is 𝛤𝑖 (𝑑−𝑖 ) on all its possible inputs (𝑥𝑖 ,𝑦𝑖 ). 3. 𝛤𝑖 does nothing but invoking 𝛤 on the same input distribution 𝜇 𝑛 . □ Now we have 𝐼(𝛤; 𝑋𝑌|𝐷) ≥ ∑𝐄𝑑−𝑖 [𝐼(𝛤𝑖 (𝑑−𝑖 );𝑋𝑖𝑌𝑖 |𝐷𝑖 )] 𝑛 𝑖=1 . Next we show that any worst-case ε-error private-coin protocol for 𝑔 has to contain a constant amount of information about (𝑋𝑖 ,𝑌𝑖 ) (conditioned on 𝐷𝑖 ). Lemma 2.3. For any worst-case ε-error private-coin protocol for 𝑔 with transcript 𝛱, 𝐼(𝛱; 𝑋𝑖𝑌𝑖 |𝐷𝑖 ) = Ω(1). Proof. Denote the transcript for input (𝑎, 𝑏) by 𝛱𝑎𝑏. First, we show that if the protocol doesn’t contain enough information, then 𝜫𝟎𝟎 is close to both 𝜫𝟎𝟏 and 𝜫𝟏𝟎. Thus 𝜫𝟎𝟏 is close to 𝜫𝟏𝟎. Consider the Hellinger distance: ℎ(𝑝, 𝑞) 2 = 1 −∑√𝑝𝑖𝑞𝑖 𝑖 = 1 2 ∑(√𝑝𝑖 − √𝑞𝑖 ) 2 𝑖 . We have 𝐼(𝛱; 𝑋𝑖𝑌𝑖 |𝐷𝑖 ) = 1 2 𝐼(𝛱; 𝑋𝑖𝑌𝑖 |𝐷𝑖 = 0) + 1 2 𝐼(𝛱; 𝑋𝑖𝑌𝑖 |𝐷𝑖 = 1) ≥ 1 2 ℎ(𝛱00 , 𝛱01 ) 2 + 1 2 ℎ(𝛱00 , 𝛱10 ) 2 // For 𝐵 ∼ 𝑈, 𝐼(𝐵,𝑝𝐵 ) ≥ ℎ(𝑝0 , 𝑝1 ) 2 ≥ 1 4 ℎ(𝛱10, 𝛱01 ) 2 // Cauchy-Schwartz and Triangle
Then,we will show that any communication protocol enjoys the property that h(Ily,Ily)=h(Iy,ly)for any x,y,x,y'.Thus Ioo is close to I1. The property is proven by writing down Pr[=]and Pr[=r]for any fixed y. It's not hard to see that Pr[=]is product of some function of x and some function of y.So by switching the function for x and that for y',we have that Pr[皿=y小Pr[皿y=y小=Pr[xy=YPr[Ⅲy=y小. Then by the multiplicative nature of the definition of h(p,q),one gets h(,)= h(Πxy,Lxy) Now the contradiction comes:g(0,0)g(1,1),so Ioo should be far from The best probability gap to distinguish and iswhich is upper bounded in terms of h(p,q)by the following fact:llp-qll<h(p,q)2-h(p,q)2. Putting everything together,we get Re(Disjn)=IrI 2I(T;XY ID) E=1 Ed [I(T;XiYilDi,D_i=d_i)] =XR1Ea_[I(Ti(d_d):XiYilD =12(1)=2(n. 口 References [BYJKS04]Ziv Bar-Yossef,T.S.Jayram,Ravi Kumar,D.Sivakumar,An information statistics approach to data stream and communication complexity.Journal of Computer and System Sciences,68(4),pp.702-732,2004. [CSWY01]Amit Chakrabarti,Yaoyun Shi,Anthony Wirth,and Andrew Yao,Informational complexity and the direct sum problem for simultaneous message complexity,in Proceedings of the 42nd Annual Symposium on Foundations ofComputer Science,pp. 270-278.2001 [CT06]Thomas Cover,Joy Thomas.Elements of Information Theory,Second Edition, Wiley InterScience,2006
Then, we will show that any communication protocol enjoys the property that 𝒉(𝛱𝒙𝒚 , 𝛱𝒙’𝒚’ ) = 𝒉(𝛱𝒙𝒚 ′ ,𝛱𝒙′𝒚 ) for any 𝒙, 𝒚,𝒙’, 𝒚’. Thus 𝛱𝟎𝟎 is close to 𝛱𝟏𝟏. The property is proven by writing down 𝑃𝑟[𝛱𝑥𝑦 = 𝛾] and 𝑃𝑟[𝛱𝑥’𝑦’ = 𝛾] for any fixed 𝛾. It’s not hard to see that 𝑃𝑟[𝛱𝑥𝑦 = 𝛾] is product of some function of 𝑥 and some function of 𝑦. So by switching the function for 𝑥 and that for 𝑦’, we have that 𝑃𝑟[𝛱𝑥𝑦 = 𝛾]𝑃𝑟[𝛱𝑥’𝑦’ = 𝛾] = 𝑃𝑟[𝛱𝑥’𝑦 = 𝛾]𝑃𝑟[𝛱𝑥𝑦’ = 𝛾]. Then by the multiplicative nature of the definition of ℎ(𝑝, 𝑞), one gets ℎ(𝛱𝑥𝑦 , 𝛱𝑥’𝑦’ ) = ℎ(𝛱𝑥𝑦’ , 𝛱𝑥’𝑦 ). Now the contradiction comes: 𝒈(𝟎,𝟎) ≠ 𝒈(𝟏,𝟏), so 𝛱𝟎𝟎 should be far from 𝛱𝟏𝟏. The best probability gap to distinguish 𝛱𝑥𝑦 and 𝛱𝑥’𝑦’ is ‖𝛤00 − 𝛤11‖1 , which is upper bounded in terms of ℎ(𝑝, 𝑞) by the following fact: ‖𝑝 − 𝑞‖1 ≤ ℎ(𝑝, 𝑞)√2 − ℎ(𝑝,𝑞) 2 . □ Putting everything together, we get 𝑅𝜖 (𝐷𝑖𝑠𝑗𝑛 ) = |𝛤| ≥ 𝐼(𝛤; 𝑋𝑌|𝐷) ≥ ∑ 𝐸𝑑−𝑖 [𝐼(𝛤;𝑋𝑖𝑌𝑖 |𝐷𝑖 ,𝐷−𝑖 = 𝑑−𝑖 )] 𝑛 𝑖=1 = ∑ 𝐸𝑑−𝑖 [𝐼(𝛤𝑖 (𝑑−𝑖 );𝑋𝑖𝑌𝑖 |𝐷𝑖 )] 𝑛 𝑖=1 = ∑ Ω(1) 𝑛 𝑖=1 = Ω(𝑛). □ References [BYJKS04] Ziv Bar-Yossef, T. S. Jayram, Ravi Kumar, D. Sivakumar, An information statistics approach to data stream and communication complexity. Journal of Computer and System Sciences, 68(4), pp. 702-732, 2004. [CSWY01] Amit Chakrabarti, Yaoyun Shi, Anthony Wirth, and Andrew Yao, Informational complexity and the direct sum problem for simultaneous message complexity, in Proceedings of the 42nd Annual Symposium on Foundations of Computer Science, pp. 270-278, 2001. [CT06] Thomas Cover, Joy Thomas. Elements of Information Theory, Second Edition, Wiley InterScience, 2006