Computationally efficient codes for strongly Dobrushin-Stambler nonsymmetrizable oblivious AVCs
Dey BK, Jaggi S, Langberg M, Sarwate AD, Zhang Y. 2024. Computationally efficient codes for strongly Dobrushin-Stambler nonsymmetrizable oblivious AVCs. Proceedings of the 2024 IEEE International Symposium on Information Theory . ISIT: International Symposium on Information Theory, 1586–1591.
Download
No fulltext has been uploaded. References only!
Conference Paper
| Published
| English
Scopus indexed
Author
Dey, B. K.;
Jaggi, S.;
Langberg, M.;
Sarwate, A. D.;
Zhang, YihanISTA ![](https://research-explorer.ista.ac.at/images/icon_orcid.png)
![](https://research-explorer.ista.ac.at/images/icon_orcid.png)
Department
Abstract
We propose a concatenated code construction for a class of discrete-alphabet oblivious arbitrarily varying channels (AVCs) with cost constraints. The code has time and space complexity polynomial in the blocklength n . It uses a Reed-Solomon outer code, logarithmic blocklength random inner codes, and stochastic encoding by permuting the codeword before transmission. When the channel satisfies a condition called strong DS-nonsymmetrizability (a modified version of nonsymmetrizability originally due to Dobrushin and Stambler), we show that the code achieves a rate that for a variety of oblivious AVCs (such as classically studied error/erasure channels) match the known capacities.
Publishing Year
Date Published
2024-08-19
Proceedings Title
Proceedings of the 2024 IEEE International Symposium on Information Theory
Acknowledgement
The work of M. Langberg and A. D. Sarwate was supported in part by the US NSF under awards CCF-1909451 and CCF1909468. B. K. Dey was supported in part by the Bharti Centre
for Communication in IIT Bombay.
Page
1586-1591
Conference
ISIT: International Symposium on Information Theory
Conference Location
Athens, Greece
Conference Date
2024-07-07 – 2024-07-12
ISBN
ISSN
IST-REx-ID
Cite this
Dey BK, Jaggi S, Langberg M, Sarwate AD, Zhang Y. Computationally efficient codes for strongly Dobrushin-Stambler nonsymmetrizable oblivious AVCs. In: Proceedings of the 2024 IEEE International Symposium on Information Theory . Institute of Electrical and Electronics Engineers; 2024:1586-1591. doi:10.1109/ISIT57864.2024.10619362
Dey, B. K., Jaggi, S., Langberg, M., Sarwate, A. D., & Zhang, Y. (2024). Computationally efficient codes for strongly Dobrushin-Stambler nonsymmetrizable oblivious AVCs. In Proceedings of the 2024 IEEE International Symposium on Information Theory (pp. 1586–1591). Athens, Greece: Institute of Electrical and Electronics Engineers. https://doi.org/10.1109/ISIT57864.2024.10619362
Dey, B. K., S. Jaggi, M. Langberg, A. D. Sarwate, and Yihan Zhang. “Computationally Efficient Codes for Strongly Dobrushin-Stambler Nonsymmetrizable Oblivious AVCs.” In Proceedings of the 2024 IEEE International Symposium on Information Theory , 1586–91. Institute of Electrical and Electronics Engineers, 2024. https://doi.org/10.1109/ISIT57864.2024.10619362.
B. K. Dey, S. Jaggi, M. Langberg, A. D. Sarwate, and Y. Zhang, “Computationally efficient codes for strongly Dobrushin-Stambler nonsymmetrizable oblivious AVCs,” in Proceedings of the 2024 IEEE International Symposium on Information Theory , Athens, Greece, 2024, pp. 1586–1591.
Dey BK, Jaggi S, Langberg M, Sarwate AD, Zhang Y. 2024. Computationally efficient codes for strongly Dobrushin-Stambler nonsymmetrizable oblivious AVCs. Proceedings of the 2024 IEEE International Symposium on Information Theory . ISIT: International Symposium on Information Theory, 1586–1591.
Dey, B. K., et al. “Computationally Efficient Codes for Strongly Dobrushin-Stambler Nonsymmetrizable Oblivious AVCs.” Proceedings of the 2024 IEEE International Symposium on Information Theory , Institute of Electrical and Electronics Engineers, 2024, pp. 1586–91, doi:10.1109/ISIT57864.2024.10619362.