TY - GEN
T1 - Repeated communication and Ramsey graphs
AU - Alon, Noga
AU - Orlitsky, Alon
PY - 1994
Y1 - 1994
N2 - Studies the savings afforded by repeated use in two zero-error communication problems. 1. Channel coding: proving a correspondence between Ramsey numbers and independence numbers of normal graph powers, the authors show that some channels can communicate exponentially more bits in two uses than they can in one use, and that this is essentially the largest possible increase. Using probabilistic constructions of self-complementary Ramsey graphs, the authors show that similar results hold even when the number of transmissible bits is large relative to the channel's size. 2. Dual-source coding: using probabilistic colorings of directed line graphs, the authors show that there are dual sources where communicating one instance requires arbitrarily many bits, yet communicating many instances requires at most two bits per instance. For dual sources where the number of bits required for a single instance is comparable to the source's size, they employ probabilistic constructions of self-complementary Ramsey graphs that are also Cayley graphs to show that conveying two instances may require only a logarithmic number of additional bits over that needed to convey one instance.
AB - Studies the savings afforded by repeated use in two zero-error communication problems. 1. Channel coding: proving a correspondence between Ramsey numbers and independence numbers of normal graph powers, the authors show that some channels can communicate exponentially more bits in two uses than they can in one use, and that this is essentially the largest possible increase. Using probabilistic constructions of self-complementary Ramsey graphs, the authors show that similar results hold even when the number of transmissible bits is large relative to the channel's size. 2. Dual-source coding: using probabilistic colorings of directed line graphs, the authors show that there are dual sources where communicating one instance requires arbitrarily many bits, yet communicating many instances requires at most two bits per instance. For dual sources where the number of bits required for a single instance is comparable to the source's size, they employ probabilistic constructions of self-complementary Ramsey graphs that are also Cayley graphs to show that conveying two instances may require only a logarithmic number of additional bits over that needed to convey one instance.
UR - http://www.scopus.com/inward/record.url?scp=84894339498&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84894339498&partnerID=8YFLogxK
U2 - 10.1109/ISIT.1994.394703
DO - 10.1109/ISIT.1994.394703
M3 - Conference contribution
AN - SCOPUS:84894339498
SN - 0780320158
SN - 9780780320154
T3 - IEEE International Symposium on Information Theory - Proceedings
SP - 315
BT - Proceedings - 1994 IEEE International Symposium on Information Theory, ISIT 1994
PB - Institute of Electrical and Electronics Engineers Inc.
T2 - 1994 IEEE International Symposium on Information Theory, ISIT 1994
Y2 - 27 June 1994 through 1 July 1994
ER -