On Linear Index Coding for Random Graphs

Computer Science – Information Theory

Scientific paper

Rate now

  [ 0.00 ] – not rated yet Voters 0   Comments 0

Details

16 pages

Scientific paper

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.

No associations

LandOfFree

Say what you really think

Search LandOfFree.com for scientists and scientific papers. Rate them and share your experience with other people.

Rating

On Linear Index Coding for Random Graphs does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with On Linear Index Coding for Random Graphs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and On Linear Index Coding for Random Graphs will most certainly appreciate the feedback.

Rate now

     

Profile ID: LFWR-SCP-O-175274

  Search
All data on this website is collected from public sources. Our data reflects the most accurate information available at the time of publication.