Abstract

An index coding (IC) problem consisting of a server and multiple receivers with different side-information and demand sets can be equivalently represented using a fitting matrix. A scalar linear index code to a given IC problem is a matrix representing the transmitted linear combinations of the message symbols. The length of an index code is then the number of transmissions (or equivalently, the number of rows in the index code). An IC problem Iext is called an extension of another IC problem I if the fitting matrix of I is a submatrix of the fitting matrix of Iext. We first present a straightforward m-order extension Iext of an IC problem I for which an index code is obtained by concatenating m copies of an index code of I. The length of the codes is the same for both I and Iext, and if the index code for I has optimal length then so does the extended code for Iext. More generally, an extended IC problem of I having the same …

Abstract

n Index Coding, the goal is to use a broadcast channel as efficiently as possible to communicate information from a source to multiple receivers which can possess some of the information symbols at the source as side-information. In this work, we present a duality relationship between index coding (IC) and multiple-unicast network coding (NC). It is known that the IC problem can be represented using a side-information graph G (with number of vertices n equal to the number of source symbols). The size of the maximum acyclic induced subgraph, denoted by MAI S is a lower bound on the broadcast rate. For IC problems with MAIS = n - 1 and MAI S = n - 2, prior work has shown that binary (over F 2) linear index codes achieve the MAI S lower bound for the broadcast rate and thus are optimal. In this work, we use the the duality relationship between NC and IC to show that for a class of IC problems with MAIS = n - 3 …

Abstract

Index coding for broadcast channels allows each receiver or client to retrieve its demanded message from its side information and the transmitted codeword. In general, a client may have to observe the entire codeword to decode its demanded message. However, downloading or querying the codeword symbols might involve costs at a client - such as network utilization costs and storage. Traditional index coding does not consider this client perspective, and as a result, for these codes the number of codeword symbols queried by a client per decoded message symbol, which we refer to as locality, could be large. In this paper we study a `client aware' approach to index coding by viewing the problem as a trade-off between the achievable broadcast rate and locality, where the objective is to minimize the rate for a given value of locality and vice versa. We first consider the minimum possible locality 1 and show that the …

Abstract

We present a coded caching framework using line graphs of bipartite graphs. A clique cover of the line graph describes the uncached subfiles at users. A clique cover of the complement of the square of the line graph gives a transmission scheme that satisfies user demands. We then define a specific class of such caching line graphs, for which the subpacketization, rate, and uncached fraction of the coded caching problem can be captured via its graph theoretic parameters. We present a construction of such caching line graphs using projective geometry. The presented scheme has a rate bounded from above by a constant with subpacketization level q O((IogqK)^2) and uncached fraction Θ(1/√K), where K is the number of users and q is a prime power. We also present a subpacketization-dependent lower bound on the rate of coded caching schemes for a given broadcast setup.

Abstract

An index coding (IC) problem consisting of a server and multiple receivers with different side-information and demand sets can be equivalently represented using a fitting matrix.A scalar linear index code to a given IC problem is a matrix representing the transmitted linear combinations of the message symbols. The length of an index code is then the number of transmissions (or equivalently, the number of rows in the index code). An IC problem I ext is called an extension of another IC problem I if the fitting matrix of Iis a sub matrix of the fitting matrix of I ext. We first present a straight forward mordern extension Iextof an IC problem I for which an index code is obtained by concatenating m copies of an index code of I. The length of the codes is the same for both I and Iext,and if the index code for I has optimal length then so does the extended code for I ext. More generally, an extended IC problem of I having the same optimal length as I is said to be a rank-invariant extension of I. We then focus on2-order rank-invariant extensions of I, and present constructions of such extensions based on in volutory permutation matrices.

Abstract

The 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 super graph, and focus on a class of uniprior problems defined on special supergraphs known as generalized cycles in which the sizes of the demand set andthe 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 fora subclass of uniprior problems. We show the NP-hardness offinding 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

Abstract

Coded caching schemes on broadcast networks with user caches help to offload traffic from peak times to off-peak times by prefetching information from the server to the usersduring off-peak times and thus serving the users more efficiently during peak times using coded transmissions. We consider the problem of secretive coded caching which was proposed recently,in which a user should not be able to decode any information about any file that the user has not demanded. We propose a new secretive coded caching scheme which has a lower average rate compared to the existing state-of-the-art scheme, for the same memory available at the users. The proposed scheme is based one exploiting the presence of common demands between multiple users

Abstract

Linear index coding can be formulated as an inter-ference alignment problem, in which precoding vectors of theminimum possible length are to be assigned to the messagesin such a way that the precoding vector of a demand (at somereceiver) is independent of the space of the interference (non side-information) precoding vectors. An index code has rate1lif theassigned vectors are of lengthl. In this paper, we introduce thenotion of strictly rate1Lmessage subsets which must necessarilybe allocated precoding vectors from a strictlyL-dimensionalspace (L=1,2,3) in any rate13code. We develop a generalnecessary condition for rate13feasibility using intersections ofstrictly rate1Lmessage subsets. We apply the necessary conditionto show that the presence of certain interference configurationsmakes the index coding problem rate13infeasible. We alsoobtain a class of index coding problems, containing certaininterference configurations, which are rate13feasible based on theidea ofcontractionsof an index coding problem. Our necessaryconditions for rate13feasibility and the class of rate13feasibleproblems obtained subsume all such known results for rate13index coding

Abstract

An index coding problem withn messages has symmetric rate R if all n messages can be conveyed at rate R. In a recent work, a class of index coding problems for which symmetric rate13is achievable was characterised using special properties of the side-information available at the receivers. In this paper, we show a larger class of index coding problems(which includes the previous class of problems) for which symmetric rate13is achievable. In the process, we also obtain a stricter necessary condition for rate13feasibility than what is known in literature.

Abstract

Matroidal networks were introduced by Doughert yet al.and have been well studied in the recent past. It was shown that a network has a scalar linear network coding solution if and only if it is matroidal associated with a representable matroid. A particularly interesting feature of this development is the ability to construct (scalar and vector)linearly solvable networks using certain classes of matroids.Furthermore, it was shown through the connection between network coding and matroid theory that linear network coding is not always sufficient for general network coding scenarios.The current work attempts to establish a connection between matroid theory and network-error correcting and detecting codes. In a similar vein to the theory connecting matroids and network coding, we abstract the essential aspects of linear network-error detecting codes to arrive at the definition of a matroidal error detecting network(and similarly, a matroidal error correcting networkabstracting from network-error correcting codes). An acyclic network (with arbitrary sink demands) is then shown to possess a scalar linear error detecting (correcting)network code if and only if it is a matroidal error detecting(correcting) network associated with a representable matroid.Therefore, constructing such network-error correcting and detecting codes implies the construction of certain representable matroids that satisfy some special conditions, and vice versa.We then present algorithms that enable the construction of matroidal error detecting and correcting networks with a specified capability of network-error correction. Using these construction algorithms, a large class of hitherto unknown scalar linearly solvable networks with multi source, multicast,and multiple- unicast network-error correcting codes is made available for theoretical use and practical implementation,with parameters, such as number of information symbols,number of sinks, number of coding nodes, error correcting capability, and so on, being arbitrary but for computing power(for the execution of the algorithms). The complexity of the construction of these networks is shown to be comparable with the complexity of existing algorithms that design multi cast scalar linear network-error correcting codes. Finally, we also show that linear network coding is not sufficient for the general network-error correction (detection) problem with arbitrary demands. In particular, for the same number of network errors,we show a network for which there is a nonlinear network-error detecting code satisfying the demands at the sinks, where as there are no linear network-error detecting codes that do the same.