Lexicographic Products and the Power of Non-linear Network Coding
- 1 October 2011
- conference paper
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE) in 2011 IEEE 52nd Annual Symposium on Foundations of Computer Science
- p. 609-618
- https://doi.org/10.1109/focs.2011.39
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
This publication has 12 references indexed in Scilit:
- Lexicographic Products and the Power of Non-linear Network CodingPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2011
- On the relation between the Index Coding and the Network Coding problemsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2008
- XORs in the Air: Practical Wireless Network CodingIEEE/ACM Transactions on Networking, 2008
- Non-Linear Index Coding Outperforming the Linear OptimumPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2007
- Networks, Matroids, and Non-Shannon Information InequalitiesIEEE Transactions on Information Theory, 2007
- Coding on demand by an informed source (ISCOD) for efficient broadcast of different supplemental data to caching clientsIEEE Transactions on Information Theory, 2006
- On the capacity of information networksPublished by Association for Computing Machinery (ACM) ,2006
- Network Coding TheoryPublished by Now Publishers ,2006
- Insufficiency of Linear Coding in Network Information FlowIEEE Transactions on Information Theory, 2005
- Network information flowIEEE Transactions on Information Theory, 2000