Local Graph Coloring and Index Coding

arxiv: 1301.5359 · v2 · pith:EWAXAMW7new · submitted 2013-01-22 · 💻 cs.IT · cs.DM· math.IT

Local Graph Coloring and Index Coding

Karthikeyan Shanmugam , Alexandros G. Dimakis , Michael Langberg This is my paper

classification 💻 cs.IT cs.DMmath.IT

keywords indexcodinglocalcodecoloringboundgoodgraph

0 comments p. Extension

pith:EWAXAMW7 Add to your LaTeX paper

What is a Pith Number?

\usepackage{pith}
\pithnumber{EWAXAMW7}

Prints a linked pith:EWAXAMW7 badge after your title and writes the identifier into PDF metadata. Compiles on arXiv with no extra files. Learn more

read the original abstract

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.

This paper has not been read by Pith yet.

Local Graph Coloring and Index Coding

discussion (0)