Soft Minoration: Solution to Cover's Problem in the Original Discrete Memoryless Setting

In 1987, Cover raised a question about the minimum relay rate needed for achieving the maximum capacity in a symmetric discrete-memoryless relay channel. Despite the many efforts over the past and recent years, this problem was previously only solved for the binary symmetric case or the Gaussian counterpart, where arguments specialized to these particular channel distributions were used. In this paper, through different information-theoretic expansions highlighting the unique capacity-achieving output distribution, we demonstrate an interesting connection between Cover's problem and the minoration problem (i.e., lower bounding the supremum of a stochastic process) from high dimensional probability. In particular, we show that the minimum relay rate for maximum capacity in a general discrete memoryless symmetric relay channel is the conditional entropy of a certain equivalence class determined by the capacity-achieving output distribution, thus completely resolving Cover's original problem. On the probability part, the main innovation is a robust method of lower bounding a soft-max (soft-minoration), which is based on mixed-volume inequalities and estimates of the Banach-Mazur distance to subspaces of \ell_{\infty}.