Skip to content (access key 's')
Logo of Technion
Logo of CS Department
Logo of CS4People

The Taub Faculty of Computer Science Events and Talks

Theory Seminar: Linear Index Coding via Semidefinite Programming
event speaker icon
Eden Chlamtac (Tel-Aviv University)
event date icon
Wednesday, 25.05.2011, 12:30
event location icon
Room 337-8 Taub Bld.
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.