On Linear Index Coding for Random Graphs

A sender wishes to broadcast an n character word x in F^n (for a field F) to n receivers R_1,...,R_n. Every receiver has some side information on x consisting of a subset of the characters of x. The side information of the receivers is represented by a graph G on n vertices in which {i,j} is an edge if R_i knows x_j. In the index coding problem the goal is to encode x using a minimum number of characters in F in a way that enables every R_i to retrieve the ith character x_i using the encoded message and the side information. An index code is linear if the encoding is linear, and in this case the minimum possible length is known to be equal to a graph parameter called minrank (Bar-Yossef et al., FOCS'06). Several bounds on the minimum length of an index code for side information graphs G were shown in the study of index coding. However, the minimum length of an index code for the random graph G(n,p) is far from being understood. In this paper we initiate the study of the typical minimum length of a linear index code for 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 Omega(\sqrt{n}). Second, we introduce and study the following two restricted models of index coding: 1. A locally decodable index code is an index code in which the receivers are allowed to query at most q characters from the encoded message. 2. A low density index code is a linear index code in which every character of the word x affects at most q characters in the encoded message. Equivalently, it is a linear code whose generator matrix has at most q nonzero entries in each row.
Comment: 16 pages