The capacity of causal adversarial channels
Download (ext.)
Conference Paper
| Published
| English
Scopus indexed
Author
Zhang, YihanISTA
;
Jaggi, Sidharth;
Langberg, Michael;
Sarwate, Anand D.

Department
Abstract
We characterize the capacity for the discrete-time arbitrarily varying channel with discrete inputs, outputs, and states when (a) the encoder and decoder do not share common randomness, (b) the input and state are subject to cost constraints, (c) the transition matrix of the channel is deterministic given the state, and (d) at each time step the adversary can only observe the current and past channel inputs when choosing the state at that time. The achievable strategy involves stochastic encoding together with list decoding and a disambiguation step. The converse uses a two-phase "babble-and-push" strategy where the adversary chooses the state randomly in the first phase, list decodes the output, and then chooses state inputs to symmetrize the channel in the second phase. These results generalize prior work on specific channels models (additive, erasure) to general discrete alphabets and models.
Publishing Year
Date Published
2022-08-03
Proceedings Title
2022 IEEE International Symposium on Information Theory
Publisher
IEEE
Acknowledgement
The work of ADS and ML was supported in part by the US National Science Foundation under awards CCF-1909468 and CCF-1909451.
Volume
2022
Page
2523-2528
Conference
ISIT: International Symposium on Information Theory
Conference Location
Espoo, Finland
Conference Date
2022-06-26 – 2022-07-01
ISBN
ISSN
IST-REx-ID
All files available under the following license(s):
Copyright Statement:
This Item is protected by copyright and/or related rights. [...]
Link(s) to Main File(s)
Access Level

Export
Marked PublicationsOpen Data ISTA Research Explorer
Sources
arXiv 2205.06708