Minoration via mixed volumes and Cover's problem for general channels

• 成果类型: Article
• 署名作者: Liu, Jingbo
• 署名单位: University of Illinois System; University of Illinois Urbana-Champaign
• 刊物名称: PROBABILITY THEORY AND RELATED FIELDS
• ISSN/ISSBN: 0178-8051
• DOI: 10.1007/s00440-022-01111-6
• 发表日期: 2022
• 页码: 315-357
• 关键词: subspaces; SPACES; bounds

摘要

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).