Random independently and identically distributed code ensembles play a fundamental role in characterizing the limits of communication rates over different network models, with most existing coding schemes built on them. It has been shown in various problems, on the other hand, these conventional random coding schemes are outperformed by \emph{structured} ones that are well-suited to the problem of interest, resulting in strictly better communication rates. This dissertation investigates the benefits of structured codes for a wider class of network models that can be grouped into two parts. In the first part, a special code structure that is built on linearity shared by multiple senders is studied for the two conflicting canonical problems defined over multiple access channels: linear computation of codewords and message communication. For linear computation, the optimal decoding performance of such structured codes is analyzed, which yields strictly larger rates than random coding. For message communication, it is shown that the aforementioned family of structured codes can achieve the optimal tradeoff between communication rates. In the second part, a structured transmission scheme, referred to as caching, is studied to reduce the network load between a server that stores a set of file contents and users that request a file from the server. To cope with the unpredictable nature of file contents and user requests, two new caching problems are formulated. As an answer to these caching problems, a successive refinement approach is proposed to store some partial information about file contents in small increments into the memories of end users. These results motivate further research into the potential of structured codes in network communication.

Next-generation wireless networks aim to enable order-of-magnitude increases in connectivity, capacity, and speed. Such a goal can be achieved in part by utilizing larger frequency bandwidth or by deploying denser base stations. As the number of wireless devices is exploding, however, it is inevitable that multiple devices communicate over the same time and same spectrum. Consequently, improving the spectral efficiency in wireless networks with multiple senders and receivers becomes the key challenge. This dissertation investigates low-complexity channel coding techniques that implement canonical random coding schemes in network information theory, such as universal channel coding, superposition coding, rate-splitting, successive cancellation, simultaneous decoding, decode-forward relaying, compress-forward relaying, and Slepian--Wolf coding. In representative communication scenarios, such as compound channels, interference channels, broadcast channels, and relay channels, the proposed channel coding techniques achieve the best known information theoretic performance, some utilizing the recently invented polar codes and some making use of the commercial off-the shelf codes, e.g., turbo and LDPC codes. These techniques have a potential to become important building blocks towards a general theory of channel coding techniques for the next-generation high-spectral-efficiency, low-power, broad-coverage wireless communication.

Cloud radio access networks (C-RANs) have been touted as a viable alternative to

current communication network architectures for handling larger data volumes and higher

throughput requirements, in order to serve a growing number of data-hungry devices.

In this dissertation, we study information theoretic models of uplink and downlink

C-RANs and explore questions on optimal data throughputs and large-network size

asymptotics. In addition, as a rst step on the path to achieving these tradeos in

practice, we demonstrate how one can build codes for multiuser networks and provide

finite-blocklength performance guarantees by starting from single-user codes.

Originally introduced to minimize the number of transmissions in satellite communication, index coding is a canonical problem in network information theory that studies the fundamental limit and optimal coding schemes for broadcasting multiple messages to receivers with different side information. The index coding problem provides a simple yet rich model for several important engineering problems in network communication, such as content broadcasting, peer-to-peer communication, distributed caching, device-to-device relaying, and interference management. It also has close relationships to network coding, distributed storage, and guessing games.

This dissertation aims to provide a broad overview of this fascinating problem, focusing on the simplest form of unicast index coding.

A unified view on coding schemes based on algebraic, graph-theoretic, and information-theoretic approaches is presented. Although the optimal communication rate, namely, the capacity is open in general, several bounds and structural properties are established. The relationships between index coding, distributed storage, and guessing game on directed graphs are also discussed.

Next-generation wireless communication systems will have to deal with an unprecedented number of communicating users and devices while enabling orders-of-magnitude of performance improvement in speed and connectivity. With the increasingly complex network structure and the high spectral efficiency requirements, it becomes extremely inefficient to rely on traditional channel coding paradigms that do not take into account the structure of the network and its inherent properties. Unlike conventional channel coding schemes that are designed under the assumption of a single sender and a single receiver communicating over a memoryless channel, this dissertation investigates low-complexity channel coding techniques that take advantage of the number of communicating devices in a network and the inherent memory in the channel. In communication over networks, low-complexity channel coding schemes that achieve the best known information theoretic performance are constructed starting from simple coding blocks. In communication over channels with memory, practical channel coding techniques that exploit the memory in the channel are developed. In both cases, the proposed coding techniques have the potential of addressing the increasing-spectral-efficiency requirement in next-generation wireless communication systems.

In modern statistical and data science applications, the probability distribution generating the data in question is unknown (or even absent) and decisions must be taken in a purely data-driven manner. Thus motivated, in this dissertation the information-theoretic approach of universal probability is revisited and expanded upon. This approach gives us general principles and guidelines for assigning sequential probabilities to data (based on which a decision can then be made), and has been used successfully over the years to problems in compression and estimation among others. The utility of this approach is then demonstrated through three example problems, motivated by the aforementioned modern statistical applications----universal compression of graphical data, sequential prediction with side information, and universal portfolio selection with side information.

Optimal detection is one of the most fundamental problems in communication and statistical signal processing. Nevertheless, in many applications, the optimal detection problem often reduces to an NP-complete, or even NP-hard, discrete optimization problem. This research project aims to develop randomized algorithms using Monte Carlo Markov chain methods to achieve near-optimal decision-making. In particular, this project focuses on two specific applications---signal detection in multiple-in-multiple-out systems and decoding of error correction codes. For the scenarios considered, we successfully proposed fast-converging Monte Carlo Markov chain algorithms that achieve near-optimality in reasonable iterations and outperform the previously best-known methods. These results open a new approach to optimal detection.

This dissertation explores optimal algorithms employed in lattice-based cryptographic schemes. Chapter 2 focuses on optimizing discrete gaussian sampling on "gadget" and algebraic lattices. These gaussian sampling algorithms are used in lattice-cryptography's most efficient trapdoor mechanism for the SIS and LWE problems: "MP12" trapdoors. However, this trapdoor mechanism was previously not optimized and inefficient (or not proven to be statistically correct) for structured lattices (ring-SIS/LWE), lattice-cryptography's most efficient form, where the modulus is often a prime. The algorithms in this chapter achieve optimality in this regime and have (already) resulted in drastic efficiency improvement in independent implementations.

Chapter 3 digs deeper into the gadget lattice's associated algorithms. Specifically, we explore efficiently sampling a simple subgaussian distribution on gadget lattices, and we optimize LWE decoding on gadget lattices. These subgaussian sampling algorithms correspond to a randomized bit-decomposition needed in lattice-based schemes with homomorphic properties like fully homomorphic encryption (FHE). Next, we introduce a general class of "Chinese Remainder Theorem" (CRT) gadgets. These gadgets allow advanced lattice-based schemes to avoid multi-precision arithmetic when the applications modulus is larger than 64 bits.

The algorithms presented in the first two chapters improve the efficiency of many lattice-based cryptosystems: digital signature schemes, identity-based encryption schemes, as well as more advanced schemes like fully-homomorphic encryption and attribute-based encryption.

In the final chapter, we take a closer look at the random matrices used in trapdoor lattices. First, we revisit the constants in the concentration bounds of subgaussian random matrices. Then, we provide experimental evidence for a simple heuristic regarding the singular values of matrices with entries drawn from commonly used distributions in cryptography. Though the proofs in this chapter are

dense, cryptographers need a strong understanding of the singular values of these matrices since their maximum singular value determines the concrete security of the trapdoor scheme's underlying SIS problem.

This dissertation illustrates how certain information-theoretic ideas and views on learning problems can lead to new algorithms via concrete examples.The three information-theoretic strategies taken in this dissertation are (1) to abstract out the gist of a learning problem in the infinite-sample limit; (2) to reduce a learning problem into a probability estimation problem and plugging-in a "good" probability; and (3) to adapt and apply relevant results from information theory. These are applied to three topics in machine learning, including representation learning, nearest-neighbor methods, and universal information processing, where two problems are studied from each topic.

The need to measure causal influences between random variables or processes in complex networks arises throughout academic disciplines. In four parts, we here develop techniques for measuring and estimating causal influences using tools from information theory, with the explicit goal of providing context for how information theoretic perspectives on causal influence fit within the vast and interdisciplinary body of work studying causality. Throughout the dissertation, we demonstrate the utility of the proposed methods with applications to physiologic, economic, and climatological datasets.

Beginning with a focus on time series, we present a modularized approach to finding the maximum a posteriori estimate of a latent time series that obeys a dynamic stochastic model and is observed through noisy measurements. We specifically consider modern signal processing problems with non-Markov signal dynamics (e.g., group sparsity) and/or non-Gaussian measurement models (e.g., point process observation models used in neuroscience). Importantly, this framework can be leveraged in the estimation of the latent parameters specifying the probability distribution of a time series, which is a fundamental step in the estimation of causal influences between time series.

Second, we study the conditions under which directed information, a popular information theoretic notion of causal influence between time series, can be estimated without bias. While the assumptions made by estimators of directed information are often presented explicitly, a characterization of when we can expect these assumptions to hold is lacking. Using the concept of d-separation from Bayesian networks, we present sufficient and almost everywhere necessary conditions for which proposed estimators can be implemented without bias. We further introduce a notion of partial directed information, which can be used to bound the bias under a milder set of assumptions.

Third, we present a sample path dependent measure of causal influence between time series. The proposed measure is a random sequence, a realization of which enables identification of specific patterns that give rise to high levels of causal influence. We demonstrate how sequential prediction theory may be leveraged to estimate the proposed causal measure and introduce a notion of regret for assessing the performance of such estimators which we subsequently bound.

Finally, we extend our focus to general causal graphs and show that information theoretic measures of causal influence are fundamentally different from mainstream (e.g. statistical) notions in that they (1) compare distributions over the effect rather than values of the effect and (2) are defined with respect to random variables representing a cause rather than specific values of a cause. We leverage perspectives from the statistical causality literature to present a novel information theoretic framework for measuring direct, indirect, and total causal effects in natural complex networks. In addition to endowing information theoretic approaches with an enhanced "resolution," the proposed framework uniquely elucidates the relationship between the information theoretic and statistical perspectives on causality.