IIIT Hyderabad Publications |
|||||||||
|
Uniprior Index CodingAuthors: hari.hara ,Chugh Ishani,Prasad Krishnan Conference: 2017 IEEE International Symposium on Information Theory (ISIT) Date: 2017-06-25 Report no: IIIT/TR/2017/138 AbstractThe index coding problem is a problem of efficient broadcasting with side-information. In uniprior index coding, the sets of side-information symbols possessed by different receivers are disjoint. For single uniprior index coding, in which each receiver has a single unique side-information symbol, a polynomial complexity construction of an optimal index code is known from prior work. In this work, we model the uniprior index coding problem as a supergraph, and focus on a class of uniprior problems defined on special supergraphs known as generalized cycles in which the sizes of the demand set and the side-information set are equal at each receiver. For such problems, we prove upper and lower bounds on the optimal broadcast rate. Using a connection with Eulerian directed graphs, we also show that the upper and lower bounds are equal for a subclass of uniprior problems. We show the NP-hardness of finding the lower bound for uniprior problems on generalized cycles, hence contrasting such uniprior problems with single uniprior problems. Finally, we look at a simple extension of the generalized cycle uniprior class for which we give bounds on the optimal rate and show an explicit scheme which achieves the upper bound. Full paper: pdf Centre for Communications |
||||||||
Copyright © 2009 - IIIT Hyderabad. All Rights Reserved. |