Average-case interactive communication
- 1 January 1992
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Information Theory
- Vol. 38 (5) , 1534-1547
- https://doi.org/10.1109/18.149503
Abstract
X and Y are random variables. Person Px knows X, Person Py knows Y, and both know the joint probability distribution of the pair (X,Y). Using a predetermined protocol, they communicate over a binary error-free channel in order for Py to learn X. Px may or may not learn Y. It is determined how many information bits must be transmitted (by both persons) on the average. The results show that, when the arithmetic average number of bits is considered, there is no asymptotic advantage to Px knowing Y in advance and four messages are asymptotically optimum. By contrast, for the worst-case number of bits, communication can be significantly reduced if Px knows Y in advance, and it is not known whether a constant number of messages is asymptotically optimumKeywords
This publication has 14 references indexed in Scilit:
- Constructing O(n Log n) Size Monotone Formulae For The k-th Elementary Symmetric Polynomial Of n Boolean VariablesPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2005
- Interactive communication: balanced distributions, correlated files, and average-case complexityPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2002
- Elements of Information TheoryPublished by Wiley ,2001
- Worst-case interactive communication. II. Two messages are not optimalIEEE Transactions on Information Theory, 1991
- Rounds in communication complexity revisitedPublished by Association for Computing Machinery (ACM) ,1991
- Worst-case interactive communication. I. Two messages are almost optimalIEEE Transactions on Information Theory, 1990
- Fredman–Komlós bounds and information theorySIAM Journal on Algebraic Discrete Methods, 1986
- Storing a Sparse Table with 0 (1) Worst Case Access TimeJournal of the ACM, 1984
- On the Size of Separating Systems and Families of Perfect Hash FunctionsSIAM Journal on Algebraic Discrete Methods, 1984
- Universal codeword sets and representations of the integersIEEE Transactions on Information Theory, 1975