Source coding and graph entropies
- 1 September 1996
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Information Theory
- Vol. 42 (5) , 1329-1339
- https://doi.org/10.1109/18.532875
Abstract
A sender wants to accurately convey information to a receiver who has some, possibly related, data. We study the expected number of bits the sender must transmit for one and for multiple instances in two communication scenarios and relate this number to the chromatic and Korner (1973) entropies of a naturally defined graph.Keywords
This publication has 14 references indexed in Scilit:
- Amortized communication complexityPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2002
- Better bounds for threshold formulasPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2002
- Elements of Information TheoryPublished by Wiley ,2001
- Entropy splitting for antiblocking corners and perfect graphsCombinatorica, 1990
- Worst-case interactive communication. I. Two messages are almost optimalIEEE Transactions on Information Theory, 1990
- Optimal separations between concurrent-write parallel machinesPublished by Association for Computing Machinery (ACM) ,1989
- New Bounds for Perfect Hashing via Information TheoryEuropean Journal of Combinatorics, 1988
- Fredman–Komlós bounds and information theorySIAM Journal on Algebraic Discrete Methods, 1986
- The zero-error side information problem and chromatic numbers (Corresp.)IEEE Transactions on Information Theory, 1976
- An upper bound on the entropy seriesInformation and Control, 1972