Constructing Index Codes with Coded Demands and Side Information through Matrix Completion We consider the problem of constructing index codes that maximize network throughput. In index coding, multiple users, with some side information, demand certain subsets of data from a server. The goal of index code is to minimize the required transmission rate at the server while ensuring that the users can recover the demanded data using the index coded broadcast message from the server. We consider a generalized version of the index coding problem, where both the side information and userdemanded data can be coded. The problem of index code construction for a given set of side information and usersxe2x80x99 demands, can be modeled as a matrix completion problem. Traditional matrix completion algorithms do not take advantage of the inherent structure in the index codes to construct efficient index codes. In this paper, using generalized proximal gradient and lowrank matrix factorization approaches, we develop matrix completion algorithms that take into account the structure in the index coding problem to construct efficient index codes. Through numerical simulations, we show that the proposed matrix completion methods construct efficient index codes compared to the traditional methods known in the literature so far.

A FieldSize Independent Code Construction for Groupcast Index Coding Problems The length of an optimal scalar linear index code of a groupcast index coding problem is equal to the minrank of its sideinformation hypergraph. The sideinformation hypergraph becomes a sideinformation graph for a special class of groupcast index coding problems known as unicast index coding problems. The number of computations required to find the minrank of a sideinformation graph depends on the number of edges present in the sideinformation graph. In this paper, we define the notion of minrankcritical edges in a sideinformation graph and derive some properties of minrank, which identifies minranknoncritical edges. Using these properties we present a method to reduce the number of computations required to compute minrank. Apart from this, we give a heuristic method to compute minrank. Also, we give an heuristic algorithm to find a clique cover of the sideinformation graph by using some binary operations on the adjacency matrix of the sideinformation graph. We also give a method to convert a groupcast index coding problem into a single unicast index coding problem. Combining all these results, we give a method to construct index codes (with not necessarily optimal length) for groupcast index coding problems. The construction technique is independent of field size and hence can be used to construct index codes over the binary field. In some cases the constructed index codes are better than the best known in the literature both in terms of the length of the code and the minimum field size required.