0
$\begingroup$

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.

$\endgroup$

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.