Unearthing the impact of structure in data and in topology for caching and computing networks

Caching has shown to be an excellent expedient for the purposes of reducing the traffic load in data networks. An information-theoretic study of caching, known as coded caching, represented a key breakthrough in understanding how memory can be effectively transformed into data rates. Coded caching also revealed the deep connection between caching and computing networks, which similarly show the same need for novel algorithmic solutions to reduce the traffic load. Despite the vast literature, there remain some fundamental limitations, whose resolution is critical. For instance, it is well-known that the coding gain ensured by coded caching not only is merely linear in the overall caching resources, but also turns out to be the Achilles heel of the technique in most practical settings. This thesis aims at improving and deepening the understanding of the key role that structure plays either in data or in topology for caching and computing networks. First, we explore the fundamental limits of caching under some information-theoretic models that impose structure in data, where by this we mean that we assume to know in advance what data are of interest to whom. Secondly, we investigate the impressive ramifications of having structure in network topology. Throughout the manuscript, we also show how the results in caching can be employed in the context of distributed computing.