Technical Program

Paper Detail

Paper Title Locality in Index Coding for Large Min-Rank
Paper IdentifierMO4.R2.1
Authors Lakshmi Natarajan, Indian Institute of Technology, Hyderabad, India; Hoang Dau, RMIT University, Australia; Prasad Krishnan, V. Lalitha, International Institute of Information Technology, Hyderabad (IIIT H), India
Session Index Coding I
Location Saint Germain, Level 3
Session Time Monday, 08 July, 16:40 - 18:00
Presentation Time Monday, 08 July, 16:40 - 17:00
Manuscript  Click here to download the manuscript
Abstract An index code is said to be 'locally decodable' if each receiver can decode its demand using its side information and by querying only a subset of the transmitted codeword symbols instead of observing the entire codeword. Local decodability can be a beneficial feature in some communication scenarios, such as when the receivers can afford to listen to only a part of the transmissions because of limited availability of power. The 'locality' of an index code is the ratio of the maximum number of codeword symbols queried by a receiver to the message length. In this paper we analyze the optimum locality of linear codes for the family of index coding problems whose min-rank is one less than the number of receivers in the network. We first derive the optimal trade-off between the index coding rate and locality with vector linear coding when the side information graph is a directed cycle. We then provide the optimal trade-off achieved by scalar linear coding for a larger family of problems, viz. problems where the min-rank is only one less than the number of receivers. While the arguments used for achievability are based on known coding techniques, the converse arguments rely on new results on the structure of locally decodable index codes.