Lexicographic products and the power of non-linear network coding

Anna Blasiak, Robert Kleinberg, Eyal Lubetzky

Research output: Chapter in Book/Report/Conference proceedingConference contribution

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.

Original languageEnglish (US)
Title of host publicationProceedings - 2011 IEEE 52nd Annual Symposium on Foundations of Computer Science, FOCS 2011
Pages609-618
Number of pages10
DOIs
StatePublished - 2011
Event2011 IEEE 52nd Annual Symposium on Foundations of Computer Science, FOCS 2011 - Palm Springs, CA, United States
Duration: Oct 22 2011Oct 25 2011

Publication series

NameProceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS
ISSN (Print)0272-5428

Other

Other2011 IEEE 52nd Annual Symposium on Foundations of Computer Science, FOCS 2011
CountryUnited States
CityPalm Springs, CA
Period10/22/1110/25/11

Keywords

  • index coding
  • information inequalities
  • lexicographic products
  • matroids
  • network coding

ASJC Scopus subject areas

  • Computer Science(all)

Fingerprint Dive into the research topics of 'Lexicographic products and the power of non-linear network coding'. Together they form a unique fingerprint.

Cite this