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))$

  • $\begingroup$ 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. $\endgroup$ – usul Jun 8 at 17:05
  • $\begingroup$ @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? $\endgroup$ – user135743 Jun 8 at 18:15

I agree that the definition you suggest is more natural. However, this definition is equivalent to the definition without the private randomness, so I assume they omit the private randomness just to have a shorter notation.

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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.