Name
Abstract | ||
|---|---|---|
Adler and Maggs [FOCS'98, 1998, 522] 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)/(log2 3 - 2/3) + 1 ≈ 1.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. |
Year | DOI | Venue |
|---|---|---|
2002 | 10.1016/S0020-0190(01)00332-5 | Inf. Process. Lett. |
Keywords | Field | DocType |
asymmetric communication protocol,probability d,expected number,improved bound,asymmetric communication channel,communication protocol,upper bound,communication channels,wireless network,wireless networking,analysis of algorithms,data compression | Wireless network,Discrete mathematics,Combinatorics,Upper and lower bounds,Computer science,Analysis of algorithms,Communication channel,Expected value,Transmission protocol,Data compression,Communications protocol | Journal |
Volume | Issue | ISSN |
83 | 4 | 0020-0190 |
Citations | PageRank | References |
9 | 0.79 | 1 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Eduardo Sany Laber | 1 | 229 | 27.12 |
| Leonardo Gomes Holanda | 2 | 9 | 1.13 |