Eden Chlamtac (Tel-Aviv University)
Wednesday, 25.5.2011, 12:30
In the index coding problem, introduced by Birk and Kol (INFOCOM, 1998), the goal is to transmit n bits to n receivers (one bit to
each), where the receivers reside at the nodes of a graph G and have prior access to the bits corresponding to their neighbors in the graph (side information). The objective is to find a code word of minimum length which will allow each receiver to learn their own bit given access to the code word and their side information. When the encoding is linear (this is known as linear index coding), the minimum possible code word length corresponds to a graph parameter known as the minrank of G.
In this talk, we will describe an algorithm which approximates the
minrank of a graph in the following sense: when the minrank of the
graph is a constant k, the algorithm finds a linear index code of
length O(n^(f(k))). For example, for k=3 we have f(3) ~ 0.2574. This
algorithm exploits a connection between minrank and a semidefinite programming (SDP) relaxation for graph coloring introduced by Karger,Motwani and Sudan.
A result which arises from our analysis, and which may be of
independent interest, gives an exact expression for the maximum
possible value of the Lovasz theta-function of a graph, as a function
of its minrank. This compares two classical upper bounds on the
Shannon capacity of a graph.