We study the problem of finding the maximum success probability for transmitting messages over a noisy channel from an algorithmic point of view. In particular, we show that a simple greedy polynomial-time algorithm computes a code achieving a (1-1/e)-approximation of the maximum success probability and that it is NP-hard to obtain an approximation ratio strictly better than (1-1/e). Moreover, the natural linear programming relaxation of this problem corresponds to the Polyanskiy-Poor-Verdú bound, which we also show has a value of at most 1/(1-1/e) times the maximum success probability.

Based on joint work with Siddharth Barman. arXiv:1508.04095