OpenAIRE is about to release its new face with lots of new content and services.
During September, you may notice downtime in services, while some functionalities (e.g. user registration, login, validation, claiming) will be temporarily disabled.
We apologize for the inconvenience, please stay tuned!
For further information please contact helpdesk[at]

fbtwitterlinkedinvimeoflicker grey 14rssslideshare1
Elkayam, Nir; Feder, Meir (2015)
Languages: English
Types: Preprint
Subjects: Computer Science - Information Theory
A minimax-converse has been suggested for the general channel coding problem by Polyanskiy etal. This converse comes in two flavors. The first flavor is generally used for the analysis of the coding problem with non-vanishing error probability and provides an upper bound on the rate given the error probability. The second flavor fixes the rate and provides a lower bound on the error probability. Both converses are given as a min-max optimization problem of an appropriate binary hypothesis testing problem. The properties of the first converse were studies by Polyanskiy and a saddle point was proved. In this paper we study the properties of the second form and prove that it also admits a saddle point. Moreover, an algorithm for the computation of the saddle point, and hence the bound, is developed. In the DMC case, the algorithm runs in a polynomial time.
  • The results below are discovered through our pilot algorithms. Let us know how we are doing!

    • [1] Y. Polyanskiy, H. V. Poor, and S. Verdu´, “Channel coding rate in the finite blocklength regime,” Information Theory, IEEE Transactions on, vol. 56, no. 5, pp. 2307-2359, 2010.
    • [2] Y. Polyanskiy, “Saddle point in the minimax converse for channel coding,” Information Theory, IEEE Transactions on, vol. 59, no. 5, pp. 2576-2595, 2013.
    • [3] N. Elkayam and M. Feder, “Achievable and converse bounds over a general channel and general decoding metric,” arXiv preprint arXiv:1411.0319, 2014. [Online]. Available:∼elkayam/FiniteBlockLen.pdf
    • [4] --. (2016) Variational formulas for the power of the binary hypothesis testing problem with applications. [Online]. Available:∼elkayam/Binary ISIT.pdf
    • [5] K. Fan, “Minimax theorems,” Proceedings of the National Academy of Sciences of the United States of America, vol. 39, no. 1, p. 42, 1953.
    • [6] W. Matthews, “A linear program for the finite block length converse of polyanskiy-poor-verdu´ via nonsignaling codes,” Information Theory, IEEE Transactions on, vol. 58, no. 12, pp. 7036-7044, 2012.
    • [7] I. Csisza´r, “The method of types [information theory],” Information Theory, IEEE Transactions on, vol. 44, no. 6, pp. 2505-2523, 1998.
    • [8] I. Csisza´r and J. Ko¨rner, Information Theory: Coding Theorems for Discrete Memoryless Systems. Cambridge University Press, 2011. [Online]. Available:
  • No related research data.
  • No similar publications.

Share - Bookmark

Cite this article

Collected from

Cookies make it easier for us to provide you with our services. With the usage of our services you permit us to use cookies.
More information Ok