Lexicographic products and the power of non-linear network coding

Abstract

We introduce a technique for establishing and amplifying gaps between parameters of network coding and index coding. The technique uses linear programs to establish separations between combinatorial and coding-theoretic parameters and applies hypergraph lexicographic products to amplify these separations. This entails combining the dual solutions of the lexicographic multiplicands and proving that they are a valid dual of the product. Our result is general enough to apply to a large family of linear programs. This blend of linear programs and lexicographic products gives a recipe for constructing hard instances in which the gap between combinatorial or coding-theoretic parameters is polynomially large. We find polynomial gaps in cases in which the largest previously known gaps were only small constant factors or entirely unknown. Most notably, we show a polynomial separation between linear and non-linear network coding rates. This involves exploiting a connection between matroids and index coding to establish a previously unknown separation between linear and non-linear index coding rates. We also construct index coding problems with a polynomial gap between the broadcast rate and the trivial lower bound for which no gap was previously known.

29 pages

References in corpus (1)

• Broadcasting with side information

Cited by in corpus (7)

• Topological Interference Management through Index Coding
• An Equivalence between Network Coding and Index Coding
• Fundamental Limits of Caching
• A Survey on Hypergraph Products (Erratum)
• Multiround Private Information Retrieval: Capacity and Storage Overhead
• Index Coding Capacity: How far can one go with only Shannon Inequalities?
• Index Coding and Network Coding via Rank Minimization