  The capacity of a channel characterizes the maximum rate at which information
can be transmitted through the channel asymptotically faithfully. For a channel
with multiple senders and a single receiver, computing its sum capacity is
possible in theory, but challenging in practice because of the nonconvex
optimization involved. To address this challenge, we investigate three topics
in our study. In the first part, we study the sum capacity of a family of
multiple access channels (MACs) obtained from nonlocal games. For any MAC in
this family, we obtain an upper bound on the sum rate that depends only on the
properties of the game when allowing assistance from an arbitrary set of
correlations between the senders. This approach can be used to prove
separations between sum capacities when the senders are allowed to share
different sets of correlations, such as classical, quantum or no-signalling
correlations. We also construct a specific nonlocal game to show that the
approach of bounding the sum capacity by relaxing the nonconvex optimization
can give arbitrarily loose bounds. Owing to this result, in the second part, we
study algorithms for non-convex optimization of a class of functions we call
Lipschitz-like functions. This class includes entropic quantities, and hence
these results may be of independent interest in information theory.
Subsequently, in the third part, we show that one can use these techniques to
compute the sum capacity of an arbitrary two-sender MACs to a fixed additive
precision in quasi-polynomial time. We showcase our method by efficiently
computing the sum capacity of a family of two-sender MACs for which one of the
input alphabets has size two. Furthermore, we demonstrate with an example that
our algorithm may compute the sum capacity to a higher precision than using the
convex relaxation.
