# Why not include private randomness in internal communication information definition?

I am using https://www.cs.toronto.edu/~toni/Courses/CommComplexity2014/Lectures/lecture12.pdf as a reference.

This isn't exactly a research question but I can't find a good place to ask it.

Suppose we have $$f:X\times Y \to Z$$, $$u$$ a distribution on $$X\times Y$$, and $$\delta >0$$.

Now consider communication protocols that allow both public and private randomness- this means a distribution (the public randomness) on a set of computation trees, each node of which has a player's name, and two edges outgoing marked by $$0,1$$, and the node gets as info the private randomness of that player; the leafs have no player's name, and instead just contain the output of the protocol (an element of $$Z$$).

If $$\prod$$ is a protocol computing $$f$$ with at most $$\delta$$ error (the probabiliy space is over both inputs, public and private randomness), we let abuse of notation use $$\prod$$ as a random variable of a string of what they players said in addition to the public randomness (to clarify, it's a pair ($$R,T$$) where $$R$$ is the public random and $$T$$ the transcript). We can define its external information complexity to be $$I_{u,\delta}(X,Y;\prod)$$.

We also define the internal information complexity to be

$$I(X;\prod|Y)+I(Y;\prod|X)$$, intuitively the first summand should be what player $$B$$ (who got $$Y$$) learns about $$X$$, and similiarly for the second.

What confuses me is shouldn't we also condition on the private randomness here?

I.e $$I(X;\prod|Y,PR(Y))+I(Y;\prod|X,PR(X))$$

• I think a short answer is because we want $IC$ to be a lower bound on communication complexity, and it's clearly true for the given definition (see proof of Prop 2). It doesn't seem as obvious to me for your definition; let's see if an expert can explain if it works. – usul Jun 8 '19 at 17:05
• @usul Thanks, that is a true point, though I would be happy for an intuitive explanation that we're measuring something natural (Atm it seems kinda weird?). More of these definitions seem weird- clearly we if you have such a protocol using public randomness, then by averaging there is a deterministic with information at most that of yours (both in the external and internal settings), so the only reason to allow public randomness seems to phrase things more easily? – user135743 Jun 8 '19 at 18:15

To see the equivalence, observe that $$\begin{eqnarray} I(X; \Pi | Y, PR(Y) ) &=& I(X; \Pi, PR(Y) | Y ) - I(X; PR(Y) | Y ) \\ & = & I(X; \Pi, PR(Y) | Y ) \\ & = & I(X; \Pi | Y ) + I(X; PR(Y) | Y, \Pi ) \\ & = & I(X; \Pi | Y ) \end{eqnarray}$$ Here, the first and third equalities follow from the chain rule, the second equality follows since $$X$$ and $$PR(Y)$$ are independent even conditioned on $$Y$$, and the fourth equality follows $$X$$ and $$PR(Y)$$ are independent even conditioned on $$Y$$ and $$\Pi$$.
The last independence takes a bit of effort to verify, but it basically follows from the rectangle property of protocols (and one also needs to note that conditioning on $$Y$$ severs the possible dependence of $$X$$ and $$PR(Y)$$ given $$\Pi$$). A bit more specifically, observe that conditioned $$\Pi$$ and $$Y$$, the set of values of $$X$$ and $$PR(Y)$$ that are consistent with $$\Pi$$ and $$Y$$ form a rectangle. Since $$X$$ and $$PR(Y)$$ started as independent variables, conditioning them on being in this rectangle preserves their independence.