Improved bounds for asymmetric communication protocols.
\textit{M. Adler} and \textit{B. M. Maggs} [FOCS'98, 522 (1998)] introduced some protocols for asymmetric communication channels. For one of them, the ``computational efficient one, they prove that the expected number of bits sent by the client to the server is at most \(1.71H(D)+1,\) where \(H(D)\) is the entropy of the distribution of probability \(D\) maintained by the server. In this paper, we show that their protocol is much better. In fact, we prove that the expected number of bits sent by the client is at most \(H(D)/(\log_{2}3\frac23)+ 1\approx1.089H(D)+1\). We also argue that this upper bound is tight in the sense that there is a distribution for which this protocol does not perform any better.
- Protocols for asymmetric communication channels
- Asymmetric communication protocols via hotlink assignments
- Dynamic hotlinks
- On asymmetric communication protocols
- Dynamic Asymmetric Communication
- How to compress asymmetric communication
- Improved approximation algorithms for the average-case tree searching problem
- An approximation algorithm for binary searching in trees
- On the complexity of searching in trees and partially ordered structures
- Dynamic asymmetric communication
This page was built for publication: Improved bounds for asymmetric communication protocols.
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1853071)
