TY - GEN
T1 - Graph theory versus minimum rank for index coding
AU - Shanmugam, Karthikeyan
AU - Dimakis, Alexandros G.
AU - Langberg, Michael
PY - 2014
Y1 - 2014
N2 - We obtain novel index coding schemes and show that they provably outperform all previously known graph theoretic bounds proposed so far 1. 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.
AB - We obtain novel index coding schemes and show that they provably outperform all previously known graph theoretic bounds proposed so far 1. 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.
UR - https://www.scopus.com/pages/publications/84906545920
U2 - 10.1109/ISIT.2014.6874841
DO - 10.1109/ISIT.2014.6874841
M3 - ???researchoutput.researchoutputtypes.contributiontobookanthology.conference???
AN - SCOPUS:84906545920
SN - 9781479951864
T3 - IEEE International Symposium on Information Theory - Proceedings
SP - 291
EP - 295
BT - 2014 IEEE International Symposium on Information Theory, ISIT 2014
PB - Institute of Electrical and Electronics Engineers Inc.
T2 - 2014 IEEE International Symposium on Information Theory, ISIT 2014
Y2 - 29 June 2014 through 4 July 2014
ER -