  Random coding arguments are the backbone of most channel capacity
achievability proofs. In this paper, we show that in their standard form, such
arguments are insufficient for proving some network capacity theorems:
structured coding arguments, such as random linear or lattice codes, attain
higher rates. Historically, structured codes have been studied as a stepping
stone to practical constructions. However, K\"{o}rner and Marton demonstrated
their usefulness for capacity theorems through the derivation of the optimal
rate region of a distributed functional source coding problem. Here, we use
multicasting over finite field and Gaussian multiple-access networks as
canonical examples to demonstrate that even if we want to send bits over a
network, structured codes succeed where simple random codes fail. Beyond
network coding, we also consider distributed computation over noisy channels
and a special relay-type problem.
