On linear index coding for random graphs

Abstract

In the index coding problem, the goal is to transmit an n character word over a field F to n receivers (one character per receiver), where the receivers have side information represented by a graph G. The objective is to minimize the length of a codeword broadcasted to all receivers which allows each receiver to learn its character. For linear index coding, the minimum possible length is known to be equal to the minrank parameter. In this paper we initiate the study of the typical minimum length of a linear index code for the random graph G(n, p) over a field F. First, we prove that for every constant size field F and a constant p, the minimum length of a linear index code for G(n, p) over F is almost surely Ω(√n). Second, we introduce and study two special models of index coding and study their typical minimum length: Locally decodable index codes in which the receivers are required to query at most q characters from the encoded message (such codes naturally correspond to efficient decoding); and low density index codes in which every character of the broadcasted word affects at most q characters in the encoded message (such codes naturally correspond to efficient encoding procedures). We present enhanced results for these special models.