Computer Science – Information Theory
Scientific paper
2011-08-11
Computer Science
Information Theory
29 pages
Scientific paper
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.
Blasiak Anna
Kleinberg Robert
Lubetzky Eyal
No associations
LandOfFree
Lexicographic products and the power of non-linear network coding does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Lexicographic products and the power of non-linear network coding, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Lexicographic products and the power of non-linear network coding will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-276745