The Taub Faculty of Computer Science Events and Talks

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.