Paper by Erik D. Demaine

Reference:

Micah Adler, Erik D. Demaine, Nicholas J. A. Harvey, and Mihai Pǎtraşcu, “Lower Bounds for Asymmetric Communication Channels and Distributed Source Coding”, in Proceedings of the 17th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2006), Miami, Florida, January 22–24, 2006, pages 251–260.

Abstract:

We prove nearly tight lower bounds on the number of rounds of communication required by efficient protocols over asymmetric channels between a server (with high sending capacity) and one or more clients (with low sending capacity). This scenario captures the common asymmetric communication bandwidth between broadband Internet providers and home users, as well as sensor networks where sensors (clients) have limited capacity because of the high power requirements for long-range transmissions. An efficient protocol in this setting communicates n bits from each of the k clients to the server, where the clients' bits are sampled from a joint distribution D that is known to the server but not the clients, with the clients sending only O(H(D) + k) bits total, where H(D) is the entropy of distribution D. In the single-client case, there are efficient protocols using O(1) rounds in expectation and O(lg n) rounds in the worst case. We prove that this is essentially best possible: with probability 1/2^O(t lg t), any efficient protocol can be forced to use t rounds. In the multi-client case, there are efficient protocols using O(lg k) rounds in expectation. We prove that this is essentially best possible: with probability Ω(1), any efficient protocol can be forced to use Ω(lg k / lg lg k) rounds. Along the way, we develop new techniques of independent interest for proving lower bounds in communication complexity.

Availability:

The paper is available in PostScript (560k), gzipped PostScript (232k), and PDF (289k).

See information on file formats.

[Google Scholar search]