Zero-Error Communication over Adversarial MACs

Abstract

We consider zero-error communication over a two-transmitter deterministic adversarial multiple access channel (MAC) governed by an adversary who has access to the transmissions of both senders (hence called omniscient) and aims to maliciously corrupt the communication. None of the encoders, jammer and decoder is allowed to randomize using private or public randomness. This enforces a combinatorial nature of the problem. Our model covers a large family of channels studied in the literature, including all deterministic discrete memoryless noisy or noiseless MACs. In this work, given an arbitrary two-transmitter deterministic omniscient adversarial MAC, we characterize when the capacity region 1) has nonempty interior (in particular, is two-dimensional); 2) consists of two line segments (in particular, has empty interior); 3) consists of one line segment (in particular, is one-dimensional); 4) or only contains $(0,0)$ (in particular, is zero-dimensional). This extends a recent result by Wang, Budkuley, Bogdanov and Jaggi (2019) from the point-to-point setting to the multiple access setting. Indeed, our converse arguments build upon their generalized Plotkin bound and involve delicate case analysis. One of the technical challenges is to take care of both "joint confusability" and "marginal confusability". In particular, the treatment of marginal confusability does not follow from the point-to-point results by Wang et al. Our achievability results follow from random coding with expurgation.

References in corpus (10)

• The Third-Order Term in the Normal Approximation for the AWGN Channel
• On the Dispersions of Three Network Information Theory Problems
• A Nonstochastic Information Theory for Communication and State Estimation
• The Arbitrarily Varying Multiple-Access Channel with Conferencing Encoders
• Quadratically Constrained Two-way Adversarial Channels
• Tight List-Sizes for Oblivious AVCs under Constraints
• Zero-error communication over adder MAC
• State Estimation over Worst-Case Erasure and Symmetric Channels with Memory
• Bounded State Estimation over Finite-State Channels: Relating Topological Entropy and Zero-Error Capacity
• List Decoding for Oblivious Arbitrarily Varying MACs: Constrained and Gaussian