I feel like many places don't explicitly mention the definition of the internal and external information of a protocol (including the original paper in academia introducing it...), and would like to verify my understanding. I thought of posting to theory exchange, but it isn't a research question.

See for instance https://www.cs.toronto.edu/~toni/Courses/CommComplexity2014/Lectures/lecture12.pdf

If I understand correctly:

We have a distribution $u$ on $A\times B$, the inputs.

We also have private for for our two players Alice and Bob, $R_1,R_2$

We also have public randomness $R_p$.

Finally, there is the random variable that is the transcript of the protocol, $\pi$- it contains what bits were sent.

Now consider the randomness over $u,R_1,R_2,R_p$, let $X,Y$ be the two inputs (so that $(X,Y)\in A\times B$). Then the external information is $H(X,Y;(\pi,R_p))$ (the random variables is over the large probability space I mentioned above, notice that the private randomness doesn't take part).

Similiarly, the internal information is $H(X;(\pi,R_p)|Y)+H(Y;(\pi,R_p)|X)$, again where each summand comes from the probability space mentioned above.


Your Answer

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

Browse other questions tagged or ask your own question.