Local time sharing for index coding

Abstract

A series of extensions of the index coding schemes based on time sharing by Birk and Kol, by Blasiak, Kleinberg, and Lubetzky, and by Shanmugam, Dimakis, and Langberg are presented. Each extension strictly improves upon the previous extensions as well as the existing schemes. The main idea behind these extensions is local time sharing over subproblems introduced by Shanmugam et al., in which the local side information available at each receiver is exploited to send the subproblm indices with a fewer number of transmissions. The final extension, despite being the best in this class of coding schemes, is shown to be still suboptimal, characterizing the fundamental limit of local time sharing.