Computation and communication are often treated as wholly separate problems. A communications engineer, tasked to design a multi-user system for performing computations while facing communications constraint, would almost certainly employ a version of the "separation principle." The system would employ a (distributed) source code to compress the sources into bits and a channel code to losslessly convey these bits over the noisy channel. The perceived reason for this design choice is two-fold. First, the abstraction of the sources and channel to bits lends itself to a universal, modular design. Second, it seems that the only gain from a joint source-channel design stems from exploiting the correlations between the sources.

This project considers the problem of computing functions over multiple-access channels (MACs) and show that in many cases of interest, a joint design can exploit a match between the structure of the channel and the function to be computed. In many cases of interest, a MAC output is a (deterministic) function of its inputs, corrupted by noise. By using structured source and channel codes, we can convert such a MAC into a reliable computation system. This structural gain does not hinge on the correlations between the sources and, with a perfect matching, increases the computation rate proportionally to the number of users. Furthermore, our underlying schemes are modular and depend primarily on coding techniques originally developed for their lower complexity.

Our work shows that many of the gains reaped by uncoded transmission for lossy communication over networks are also available for lossless communication when computation coding is employed. Furthermore, we show that our codes can outperform separation-based schemes even when the desired function and the underlying MAC are strongly mismatched (ex: adding over a multiplying channel). We have also demonstrated that computation codes are useful even when the problem statement does not directly call for the computation of a function. Specifically, we have characterized the multicast capacity of a class of multiple-access channel networks.