@inproceedings{8063431349d54f1ca11b66785b15c763,

title = "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 problems. The technique uses linear programs to establish separations between combinatorial and coding-theoretic parameters and applies hyper graph lexicographic products to amplify these separations. This entails combining the dual solutions of the lexicographic multiplicands and proving that this is a valid dual solution 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.",

keywords = "index coding, information inequalities, lexicographic products, matroids, network coding",

author = "Anna Blasiak and Robert Kleinberg and Eyal Lubetzky",

year = "2011",

doi = "10.1109/FOCS.2011.39",

language = "English (US)",

isbn = "9780769545714",

series = "Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS",

pages = "609--618",

booktitle = "Proceedings - 2011 IEEE 52nd Annual Symposium on Foundations of Computer Science, FOCS 2011",

note = "2011 IEEE 52nd Annual Symposium on Foundations of Computer Science, FOCS 2011 ; Conference date: 22-10-2011 Through 25-10-2011",

}