On the separation of correlation-assisted sum capacities of multiple access channels

Computing the sum capacity of a multiple access channel (MAC) is a non-convex optimization problem. It is therefore common to compute an upper bound on the sum capacity using a convex relaxation. We investigate the performance of such a relaxation by considering a family of MACs obtained from nonlocal games. First, we derive an analytical upper bound on the sum capacity of such MACs, while allowing the senders to share any given set of correlations. Our upper bound depends only on the properties of the game available in practice, thereby providing a way to obtain separations between the sum capacity assisted by different sets of correlations. In particular, we obtain a bound on the sum capacity of the MAC obtained from the magic square game that is tighter than the previously known result. Next, we introduce a game for which the convex relaxation of the sum capacity can be arbitrarily loose, demonstrating the need to find other techniques to compute or bound the sum capacity. We subsequently propose an algorithm that can certifiably compute the sum capacity of any two-sender MAC to a given precision.