Repeated Communication and Ramsey Graphs

Noga Alon, Alon Orlitsky, Noga Alon

Research output: Contribution to journalArticle

43 Scopus citations

Abstract

We study the savings afforded by repeated use in two zero-error communication problems. We show that for some random sources, communicating one instance requires arbitrarily many bits, but communicating multiple instances requires roughly 1 bit per instance. We also exhibit sources where the number of bits required for a single instance is comparable to the source's size, but two instances require only a logarithmic number of additional bits. We relate this problem to that of communicating information over a channel. Known results imply that some channels can communicate exponentially more bits in two uses than they can in one use.

Original languageEnglish (US)
Pages (from-to)1276-1289
Number of pages14
JournalIEEE Transactions on Information Theory
Volume41
Issue number5
DOIs
StatePublished - Sep 1995
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Information Systems
  • Computer Science Applications
  • Library and Information Sciences

Fingerprint Dive into the research topics of 'Repeated Communication and Ramsey Graphs'. Together they form a unique fingerprint.

  • Cite this