Appears in collection : Nexus Trimester - 2016 - Distributed Computation and Communication Theme

The network information theory literature includes beautiful results describing codes and performance limits for many different networks. While common tools and themes are evident in the proofs of these results, the field is still very far from a unifying theory that not only explains how and why the optimal strategies for well-studied networks differ but also predicts solutions for networks to be studied in the future. In this talk, I will present one step towards the derivation of such a theory based on the paradigm of reduction. A reduction shows that a problem A can be solved by turning it into a different problem B and then applying a solution for B. While the notion of a reduction is extremely simple, the tool of reduction turns out to be incredibly powerful. The key to its power is the observation that reductive proofs are possible even when solutions to both A and B are unavailable. The paradigm of reduction can be used to show that a communication problem is “easy” if it can be mapped to other problems for which solutions are well understood. It can be used to show that a problem is “hard” if a notorious open problem can be reduced to it. It can be used to show that proof techniques and results from the study of one problem apply to other problems as well. It can be used to derive provable, quantifiable connections between problems that are intuitively very similar or problems that are apparently unrelated. In this talk I will give an overview of several reductive connections that have emerged recently in the literature between seemingly disparate information theoretic problems. These include connections between network coding and index coding, connections between secure and standard communication, connections between noisy and noiseless networks, and more.