TY - GEN

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

AU - Seshadri, Akshay

AU - Leditzky, Felix

AU - Siddhu, Vikesh

AU - Smith, Graeme

N1 - Publisher Copyright:
© 2022 IEEE.

PY - 2022

Y1 - 2022

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

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

UR - http://www.scopus.com/inward/record.url?scp=85136314327&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85136314327&partnerID=8YFLogxK

U2 - 10.1109/ISIT50566.2022.9834459

DO - 10.1109/ISIT50566.2022.9834459

M3 - Conference contribution

AN - SCOPUS:85136314327

T3 - IEEE International Symposium on Information Theory - Proceedings

SP - 2756

EP - 2761

BT - 2022 IEEE International Symposium on Information Theory, ISIT 2022

PB - Institute of Electrical and Electronics Engineers Inc.

T2 - 2022 IEEE International Symposium on Information Theory, ISIT 2022

Y2 - 26 June 2022 through 1 July 2022

ER -