Graph theory versus minimum rank for index coding
Graph theory versus minimum rank for index coding
We obtain novel index coding schemes and show that they provably outperform all previously known graph theoretic bounds proposed so far. Further, we establish a rather strong negative result: all known graph theoretic bounds are within a logarithmic factor from the chromatic number. This is in striking contrast to minrank since prior work has shown that it can outperform the chromatic number by a polynomial factor in some cases. The conclusion is that all known graph theoretic bounds are not much stronger than the chromatic number.
8 pages, 2 figures. Submitted to ISIT 2014
- The University of Texas at Austin United States
- University at Buffalo, State University of New York United States
FOS: Computer and information sciences, Computer Science - Information Theory, Information Theory (cs.IT)
FOS: Computer and information sciences, Computer Science - Information Theory, Information Theory (cs.IT)
citations This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).28 popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network.Top 10% influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).Top 10% impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network.Top 10%
Citations provided by BIP!Popularity provided by BIP!