This paper examines the problem of communicating an n-bit data item from a client to a server, where the data is drawn from a distribution D that is known to the server but not to the client. Our primary goal is to limit the number of bits transmitted by the client. We present several protocols in which the expected number of bits transmitted by the server and client are O(n) and O(H(D)), respectively, where H(D) is the entropy of D. Shannon's Theorem implies that these protocols are optimal in terms of the number of bits sent by the client. The expected number of rounds of communication between the server and client in the simplest of our protocols is O(H(D)). We also give a protocol for which the expected number of rounds is only O(1), but which requires more computational effort on the part of the server. A third protocol provides a tradeoff between the computational effort and the number of rounds. These protocols are complemented by lower bounds and impossibility results. We show that all of our protocols are existentially optimal in terms of the number of bits sent by the server, i.e., there are distributions for which the total number of bits exchanged has to be at least n - 1. In addition, we show that there is no protocol that is optimal for every distribution (as opposed to existentially optimal) in terms of bits sent by the server. We demonstrate this by proving that the problem of computing, for an arbitrary distribution D, a string of bits that the server should send to the client in order to minimize the expected total number of bits sent by the server and client is undecidable. Furthermore, the problem remains undecidable even if only an approximate solution is required, for any reasonable degree of approximation.

25 pages

*Department of Computer Science, University of Toronto, 10 King's College Road, Toronto, Ontario, M5S3G4 Canada

Return to: SCS Technical Report Collection
School of Computer Science homepage

This page maintained by reports@cs.cmu.edu