Worst case interactive communication among three parties

Abstract

This thesis extends existing work on worst-case two party interactive communication to three parties. PX, PY and PZ know random variables X, Y and Z, respectively, and all parties know the joint distribution, p(x; y; z). Using an agreed-upon protocol, the parties communicate over one or more error-free channels. The objective is for PZ to learn X and Y , and cost is measured in worst-case total information bits transmitted. In the two party case, where PZ must learn only X, interactive protocols (in which PZ may send bits) can reduce the cost to approximately the log of the cost when only PX may transmit (Orlitsky, 1990). In the three party case, PZ can learn X and Y separately, however this is not necessarily optimal. Can a three party protocol provide a cost savings over two separate two party protocols? We describe a joint protocol based on that of Naor et al. (Naor et al., 1993) for communicating X and Y in parallel and show that it can provide at most a constant factor savings. We also describe a sequential protocol in which PZ first learns Y and then uses this knowledge to reduce the cost of subsequently learning X. Although there are input distributions for which this type of protocol can provide more substantial savings, we show that for a large fraction of all input distributions, any three party protocol can provide at most a constant factor savings over two separate two party protocols. Finally, we increase the number of parties and show that for some input distributions multi-party interaction can yield a better than constant factor savings.