TY - GEN
T1 - Local graph coloring and index coding
AU - Shanmugam, Karthikeyan
AU - Dimakis, Alexandros G.
AU - Langberg, Michael
PY - 2013
Y1 - 2013
N2 - We present a novel upper bound for the optimal index coding rate. Our bound uses a graph theoretic quantity called the local chromatic number. We show how a good local coloring can be used to create a good index code. The local coloring is used as an alignment guide to assign index coding vectors from a general position MDS code. We further show that a natural LP relaxation yields an even stronger index code. Our bounds provably outperform the state of the art on index coding but at most by a constant factor.
AB - We present a novel upper bound for the optimal index coding rate. Our bound uses a graph theoretic quantity called the local chromatic number. We show how a good local coloring can be used to create a good index code. The local coloring is used as an alignment guide to assign index coding vectors from a general position MDS code. We further show that a natural LP relaxation yields an even stronger index code. Our bounds provably outperform the state of the art on index coding but at most by a constant factor.
UR - https://www.scopus.com/pages/publications/84890334511
U2 - 10.1109/ISIT.2013.6620407
DO - 10.1109/ISIT.2013.6620407
M3 - Conference contribution
AN - SCOPUS:84890334511
SN - 9781479904464
T3 - IEEE International Symposium on Information Theory - Proceedings
SP - 1152
EP - 1156
BT - 2013 IEEE International Symposium on Information Theory, ISIT 2013
T2 - 2013 IEEE International Symposium on Information Theory, ISIT 2013
Y2 - 7 July 2013 through 12 July 2013
ER -