Improved bounds for asymmetric communication protocols.
type: Item
instance of: scholarly article
title: Improved bounds for asymmetric communication protocols.
zbMATH Open document ID: 1043.68015
DOI: 10.1016/S0020-0190(01)00332-5
author: Eduardo S. Laber
author: Leonardo Gomes Holanda
published in: Information Processing Letters
publication date: 2003-01-21T00:00:00Z
review text: \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.
Mathematics Subject Classification ID: 68M12
Mathematics Subject Classification ID: 94A05
Mathematics Subject Classification ID: 94A24
zbMATH DE Number: 1856411
zbMATH Keywords: Analysis of algorithms
zbMATH Keywords: Asymmetric communication
zbMATH Keywords: Data compression
zbMATH Keywords: Wireless networking
MaRDI profile type: Publication
cites work: Protocols for asymmetric communication channels
cites work: A Method for the Construction of Minimum-Redundancy Codes
cites work: A Mathematical Theory of Communication
description: scientific article; zbMATH DE number 1856411