  Communication networks have multiple users, each sending and receiving
messages. A multiple access channel (MAC) models multiple senders transmitting
to a single receiver, such as the uplink from many mobile phones to a single
base station. The optimal performance of a MAC is quantified by a capacity
region of simultaneously achievable communication rates. We study the
two-sender classical MAC, the simplest and best-understood network, and find a
surprising richness in both a classical and quantum context. First, we find
that quantum entanglement shared between senders can substantially boost the
capacity of a classical MAC. Second, we find that optimal performance of a MAC
with bounded-size inputs may require unbounded amounts of entanglement. Third,
determining whether a perfect communication rate is achievable using
finite-dimensional entanglement is undecidable. Finally, we show that
evaluating the capacity region of a two-sender classical MAC is in fact
NP-hard.
