Minoration via Mixed Volumes and Cover's Problem for General Channels
arXiv:2012.14521 · doi:10.1007/s00440-022-01111-6
Abstract
We give a complete solution to an open problem of Thomas Cover in 1987 about the capacity of a relay channel in the general discrete memoryless setting without any additional assumptions. The key step in our approach is to lower bound a certain soft-max of a stochastic process by convex geometry methods, which is based on two ideas: First, the soft-max is lower bounded in terms of the supremum of another process, by approximating a convex set with a polytope with bounded number of vertices. Second, using a result of Pajor, the supremum of the process is lower bounded in terms of packing numbers by means of mixed-volume inequalities (Minkowski's first inequality).
Some materials in Section 3 from the previous version are removed, replaced by appropriate references to [Pajor 1984] and [Mendelson, Milman, Paouris 2019]. The paper has been published online on Probability Theory and Related Fields