An Overview of Capacity Results for Synchronization Channels. Cheraghchi, M. & Ribeiro, J. IEEE Transactions on Information Theory, 67(6):3207–3232, 2021.
An Overview of Capacity Results for Synchronization Channels [link]Link  An Overview of Capacity Results for Synchronization Channels [link]Paper  doi  abstract   bibtex   
Synchronization channels, such as the well-known deletion channel, are surprisingly harder to analyze than memoryless channels, and they are a source of many fundamental problems in information theory and theoretical computer science. One of the most basic open problems regarding synchronization channels is the derivation of an exact expression for their capacity. Unfortunately, most of the classic information-theoretic techniques at our disposal fail spectacularly when applied to synchronization channels. Therefore, new approaches must be considered to tackle this problem. This survey gives an account of the great effort made over the past few decades to better understand the (broadly defined) capacity of synchronization channels, including both the main results and the novel techniques underlying them. Besides the usual notion of channel capacity, we also discuss the zero-error capacity of adversarial synchronization channels.
@ARTICLE{ref:CR21,
  author =	 {Mahdi Cheraghchi and Jo\~{a}o Ribeiro},
  title =	 {An Overview of Capacity Results for Synchronization
                  Channels},
  journal =	 {IEEE Transactions on Information Theory},
  doi =		 {10.1109/TIT.2020.2997329},
  year={2021},
  volume={67},
  number={6},
  pages={3207--3232},
  url_Link =	 {https://ieeexplore.ieee.org/document/9099526},
  url_Paper =	 {https://arxiv.org/abs/1910.07199},
  abstract =	 {Synchronization channels, such as the well-known
                  deletion channel, are surprisingly harder to analyze
                  than memoryless channels, and they are a source of
                  many fundamental problems in information theory and
                  theoretical computer science. One of the most basic
                  open problems regarding synchronization channels is
                  the derivation of an exact expression for their
                  capacity. Unfortunately, most of the classic
                  information-theoretic techniques at our disposal
                  fail spectacularly when applied to synchronization
                  channels. Therefore, new approaches must be
                  considered to tackle this problem. This survey gives
                  an account of the great effort made over the past
                  few decades to better understand the (broadly
                  defined) capacity of synchronization channels,
                  including both the main results and the novel
                  techniques underlying them. Besides the usual notion
                  of channel capacity, we also discuss the zero-error
                  capacity of adversarial synchronization channels.  }
}

Downloads: 0