Linear Index Coding via Semidefinite Programming
Eden Chlamtáč, Ishay Haviv · Combinatorics Probability Computing · 2013
In the index coding problem, introduced by Birk and Kol ( INFOCOM, 1998 ), the goal is to broadcast an n -bit word to n receivers (one bit per receiver), where the receivers have side information represented by a graph G . The objective is to minimize the length of a codeword sent to all receivers which allows each receiver to learn its bit. For linear index coding, the minimum possible length is known to be equal to a graph parameter called minrank (Bar-Yossef, Birk, Jayram and Kol, IEEE Trans. Inform. Theory , 2011). We show a polynomial-time algorithm that, given an n -vertex graph G with minrank k , finds a linear index code for G of length Õ ( n f ( k ) ), where f ( k ) depends only on k . For example, for k = 3 we obtain f (3) ≈ 0.2574. Our algorithm employs a semidefinite program (SDP) introduced by Karger, Motwani and Sudan for graph colouring ( J. Assoc. Comput. Mach. , 1998) and its refined analysis due to Arora, Chlamtac and Charikar ( STOC , 2006). Since the SDP we use is not a relaxation of the minimization problem we consider, a crucial component of our analysis is an upper bound on the objective value of the SDP in terms of the minrank. At the heart of our analysis lies a combinatorial result which may be of independent interest. Namely, we show an exact expression for the maximum possible value of the Lovász ϑ-function of a graph with minrank k . This yields a tight gap between two classical upper bounds on the Shannon capacity of a graph.