The capacity of causal adversarial channels

conference paper The capacity of causal adversarial channels published yes Yihan Zhang author 2ce5da42-b2ea-11eb-bba5-9f264e9d002c0000-0002-6465-6258 Sidharth Jaggi author Michael Langberg author Anand D. Sarwate author MaMo department ISIT: International Symposium on Information Theory 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. IEEE2022Espoo, Finland eng 2022 IEEE International Symposium on Information Theory 2157-8095 9781665421591 2205.06708 00125426190211410.1109/ISIT50566.2022.9834709 20222523-2528 Y. Zhang, S. Jaggi, M. Langberg, and A. D. Sarwate, “The capacity of causal adversarial channels,” in 2022 IEEE International Symposium on Information Theory, Espoo, Finland, 2022, vol. 2022, pp. 2523–2528. Y. Zhang, S. Jaggi, M. Langberg, A.D. Sarwate, in:, 2022 IEEE International Symposium on Information Theory, IEEE, 2022, pp. 2523–2528. Zhang, Y., Jaggi, S., Langberg, M., & Sarwate, A. D. (2022). The capacity of causal adversarial channels. In 2022 IEEE International Symposium on Information Theory (Vol. 2022, pp. 2523–2528). Espoo, Finland: IEEE. <a href="https://doi.org/10.1109/ISIT50566.2022.9834709">https://doi.org/10.1109/ISIT50566.2022.9834709</a> Zhang, Yihan, et al. “The Capacity of Causal Adversarial Channels.” 2022 IEEE International Symposium on Information Theory, vol. 2022, IEEE, 2022, pp. 2523–28, doi:<a href="https://doi.org/10.1109/ISIT50566.2022.9834709">10.1109/ISIT50566.2022.9834709</a>. Zhang Y, Jaggi S, Langberg M, Sarwate AD. The capacity of causal adversarial channels. In: 2022 IEEE International Symposium on Information Theory. Vol 2022. IEEE; 2022:2523-2528. doi:<a href="https://doi.org/10.1109/ISIT50566.2022.9834709">10.1109/ISIT50566.2022.9834709</a> Zhang, Yihan, Sidharth Jaggi, Michael Langberg, and Anand D. Sarwate. “The Capacity of Causal Adversarial Channels.” In 2022 IEEE International Symposium on Information Theory, 2022:2523–28. IEEE, 2022. <a href="https://doi.org/10.1109/ISIT50566.2022.9834709">https://doi.org/10.1109/ISIT50566.2022.9834709</a>. Zhang Y, Jaggi S, Langberg M, Sarwate AD. 2022. The capacity of causal adversarial channels. 2022 IEEE International Symposium on Information Theory. ISIT: International Symposium on Information Theory vol. 2022, 2523–2528. 120112022-09-04T22:02:03Z2025-09-10T09:40:42Z