On the non-adaptive zero-error capacity of the discrete memoryless two-way channel

Yujie Gu, Ofer Shayevitz

Research output: Contribution to journalArticlepeer-review

2 Citations (Scopus)


We study the problem of communicating over a discrete memoryless two-way channel using non-adaptive schemes, under a zero probability of error criterion. We derive single-letter inner and outer bounds for the zero-error capacity region, based on random coding, linear programming, linear codes, and the asymptotic spectrum of graphs. Among others, we provide a single-letter outer bound based on a combination of Shannon’s vanishing-error capacity region and a two-way analogue of the linear programming bound for point-to-point channels, which, in contrast to the one-way case, is generally better than both. Moreover, we establish an outer bound for the zero-error capacity region of a two-way channel via the asymptotic spectrum of graphs, and show that this bound can be achieved in certain cases.

Original languageEnglish
Article number1518
Issue number11
Publication statusPublished - Nov 2021

All Science Journal Classification (ASJC) codes

  • Information Systems
  • Mathematical Physics
  • Physics and Astronomy (miscellaneous)
  • Electrical and Electronic Engineering


Dive into the research topics of 'On the non-adaptive zero-error capacity of the discrete memoryless two-way channel'. Together they form a unique fingerprint.

Cite this