Paper by Erik D. Demaine
- 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.
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/2O(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.
- The paper is available in PostScript (560k), gzipped PostScript (232k), and PDF (289k).
- See information on file formats.
- [Google Scholar search]
See also other papers by Erik Demaine.
These pages are generated automagically from a
Last updated July 21, 2021 by