| Understanding the fundamental limits of communication systems involves both constructing efficient coding schemes as well as proving mathematically that certain performance is impossible to achieve; the latter is known as the converse problem in information theory. This thesis focused on the converse problems for complex information systems such as self-repair distributed storage and coded caching systems, and our goal was to establish tight converse results for such systems by exploiting problem-specific combinatorial structures.;The main part of this thesis dealt with exact-repair regenerating codes, which were first proposed by Dimakis et al. in 2010. In particular, we considered two extensions of the original setting of Dimakis et al., namely 1) multilevel diversity coding with regeneration and 2) secure exact-repair regenerating codes. For the problem of multilevel diversity coding with regeneration, we showed, via the proposed combinatorial approach, that the natural separate encoding strategy can achieve the optimal tradeoff between the normalized storage capacity and repair bandwidth at the minimum-bandwidth rate (MBR) point. This settled a conjecture by Tian and Liu in 2015.;For the problem of secure exact-repair regenerating codes, all known results from the literature showed that the achievable tradeoff regions between the normalized storage capacity and repair bandwidth have a single corner point, achieved by a scheme proposed by Shah, Rashmi and Kumar (the SRK point). Since the achievable tradeoff regions of the exact-repair regenerating code problem without any secrecy constraints were known to have multiple corner points in general, these existing results suggested a phase-change-like behavior, i.e., enforcing a secrecy constraint immediately reduces the tradeoff region to one with a single corner point. In our work, we first showed that when the secrecy parameter is sufficiently large, the SRK point is indeed the only corner point of the tradeoff region. However, when the secrecy parameter is small, we showed that the tradeoff region can, in fact, have multiple corner points. In particular, we established a precise characterization of the tradeoff region for a particular problem instance, which has exactly two corner points. Thus, a smooth transition, instead of a phase-change-type of transition, should be expected as the secrecy constraint is gradually strengthened. |
