Communication over unreliable, interfering networks is one of the current challenges inengineering. For point-to-point channels, Shannon established capacity results in 1948, and it took more than forty years to find coded systems approaching the capacity limit with feasible complexity. Significant research efforts have gone into extending Shannon's capacity results to networks with many partial successes. By contrast, the development of low-complexity codes for networks has received limited attention to date.

The focus of this thesis is the design of capacity-achieving network codes realizable by modern signal processing circuits. For classes of networks, the following codes have been invented on the foundation of algebraic structure and probability theory: i ) Broadcast codes which achieve multi-user rates on the capacity boundary of several types of broadcast channels. The codes utilize Arýkan's polarization theory of random variables, providing insight into information-theoretic concepts such as random binning, superposition coding, and Marton's construction. Reproducible experiments over block lengths n = 512, 1024, 2048 corroborate the theory; ii ) A network code which achieves the computing capacities of a countably infinite class of simple noiseless interfering networks. The code separates a network into irreducible parallel sub-networks and applies a new vector-space function alignment scheme inspired by the concept of interference alignment for channel communications. New bounds are developed to tighten the standard

cut-set bound for multi-casting functions.

As an additional example of low-complexity codes, reduced-dimension linear transforms and convex optimization methods are proposed for the lossy transmission of correlated sources across noisy networks. Surprisingly, simple un-coded or one-shot strategies achieve a performance which is exactly optimal in certain networks, or close to optimal in the low signal-to-noise regime relevant for sensor networks.

The problem of recovering sparse signals from a limited number of measurements is now ubiquitous in signal processing, statistics, and machine learning. A natural question of fundamental interest is that of what can and cannot be recovered in the presence of noise. This thesis provides a sharp characterization for the task of sparsity pattern recovery (also known as support recovery). Using tools from information theory, we find a sharp separation into two problem regimes -- one in which the problem is fundamentally noise-limited, and a more interesting one in which the problem is limited by the behavior of the sparse components themselves. This analysis allows us to identify settings where existing computationally efficient algorithms, such as the LASSO or approximate message passing, are optimal as well as other settings where these algorithms are highly suboptimal. We compare our results to predictions of phase transitions made via the powerful but heuristic replica method, and find that our rigorous bounds confirm some of these predictions.

The remainder of the thesis explores extensions of our bounds to various scenarios. We consider specially structured sampling matrices and show how such additional structure can make a key difference, analogous to the role of diversity in wireless communications. Finally, we illustrate how the new bounding techniques introduced in this thesis can be used to establish information-theoretic secrecy results for certain communication channel models that involve eavesdroppers.

Though random codes are shown to be optimal for point-to-point channels, codes with algebraic structure are found to be useful in many network scenarios. This thesis demonstrates the role of structured codes in several network and MIMO settings. In MIMO channels, structured codes can be used to improve receiver design. Traditional receiver architectures decorrelate the mixed data streams and recover each of them individually. Although optimal when the channel matrix is orthogonal, this can be highly sub-optimal when the channel is near singular. To overcome this limitation, a new architecture that recovers linear combinations of the data streams instead of the data streams individually is proposed. The proposed integer-forcing receiver outperforms traditional linear architectures and achieves the optimal diversity-multiplexing tradeoff. In network information theory, it has been shown that structured codes are useful for computation over multiple-access channels. This thesis considers function computation across general relay networks and proposes a scheme that decouples the physical and network layers. By using lattice codes in the physical layer and network codes in the network layer, the proposed scheme achieves the optimal distortion to within a constant factor. Finally, structured codes can be used to efficiently transmit channel state information when global channel state information is absent in networks. It is shown that sending a function of the channel state information is sufficient and can be much more efficient than sending the full information.

In this thesis we study the data exchange problem where a set of users is interested in gaining access to a common file, but where each has only partial knowledge about it as side- information. Assuming that the file is broken into packets, the side-information considered is in the form of linear combinations of the file packets. Given that the collective information of all the users is sufficient to allow recovery of the entire file, the goal is for each user to gain access to the file while minimizing some communication cost. We assume that users can communicate over a noiseless broadcast channel, and that the communication cost is a sum of each user's cost function over the number of bits it transmits. For instance, the communication cost could simply be the total number of bits that needs to be transmitted. In the most general case studied in this thesis, each user can have any arbitrary convex cost function. We provide a polynomial time deterministic algorithm (in the number of users and packets) that finds an optimal communication scheme that minimizes the communication cost. To further lower the complexity, we also propose a simple randomized algorithm inspired by our deterministic algorithm which is based on a random linear network coding scheme. In the later chapters we consider a general form of side-information, where each user observes independent realizations of some joint random process. For such scenario, we provide a polynomial-time algorithm (in the number of users and packets) that finds an optimal communication rate allocations for all the users. Next, we study two extensions to the original data exchange problem. First, we consider the problem where not all users in the system are interested in obtaining the file, but they are willing to help users who are. Also, we explore the problem where each user can communicate only to its immediate neighbors through a wireline network. For both the problems, we provide a polynomial time algorithm that is inspired by the original data exchange problem.

In a network, interference between transmitters is usually viewed as highly undesirable and clever algorithms and protocols have been devised to avoid it. Collectively, these strategies transform the physical layer into a set of reliable bit pipes which can then be used seamlessly by higher layers in the protocol stack. Unfortunately, interference avoidance results in sharply decreasing rates as the number of users increases. In this thesis, we develop a new tool, computation coding, that allows receivers to reliably decode equations of transmitted messages by harnessing the interference structure of the channel. Applied to a wireless network, this enables relays to decode linear functions of the transmitted messages with coefficients dictated by the fading realization. Relays can then forward these equations towards the destinations which simply collect enough equations to solve for their desired messages. Structured codes (such as lattices) ensure that these linear combinations can be decoded reliably at the relays, often at far higher rates than the messages individually. Through examples drawn from cooperative communication including cellular uplink, distributed MIMO and wireless network coding, we demonstrate that this compute-and-forward strategy can improve end-to-end throughput in a network. As a consequence, we will see that structured codes can play an important role in approaching the capacity of networks. We also show that our techniques can result in both energy and delay savings for distributed signal processing over a sensor network. Finally, by viewing interference as implicit computation, we provide a new perspective on the interference channel with time-varying fading. We describe a simple interference alignment scheme that enables each user to achieve at least half its interference-free capacity at any signal-to-noise ratio.