  We address the problem of coding for classical multiple-access channels
(MACs) with the assistance of non-signaling correlations between parties. It is
well-known that non-signaling assistance does not change the capacity of
classical point-to-point channels. However, it was recently observed that one
can construct MACs from two-player non-local games while relating the winning
probability of the game to the capacity of the MAC. By considering games for
which entanglement increases the winning probability, this shows that for some
specific kinds of channels, entanglement between the senders can increase the
capacity.
  We make several contributions towards understanding the capacity region for
MACs with the assistance of non-signaling correlations. We develop a linear
program computing the optimal success probability for coding over $n$ copies of
a MAC $W$ with size growing polynomially in $n$. Solving this linear program
allows us to achieve inner bounds for MACs. Applying this method to the binary
adder channel, we show that using non-signaling assistance, the sum-rate
$1.5425$ can be reached even with zero error, which beats the maximum sum-rate
capacity of $1.5$ in the unassisted case. For noisy channels, where the
zero-error non-signaling assisted capacity region is trivial, we can use
concatenated codes to obtain achievable points in the capacity region. Applied
to a noisy version of the binary adder channel, we show that non-signaling
assistance still improves the sum-rate capacity. Complementing these
achievability results, we give an outer bound on the non-signaling assisted
capacity region that has the same expression as the unassisted region except
that the channel inputs are not required to be independent. Finally, we show
that the capacity region with non-signaling assistance shared only between each
sender and the receiver independently is the same as without assistance.
