A private information retrieval protocol (PIR) scheme under an arbitrary collusion pattern $\mathcal{P}$ enables a client to retrieve one message from a library of $K$ equal-sized messages duplicated in $N$ servers, while keeping the index of the desired message private from any colluding set in $\mathcal{P}$. Although achieving high rates typically requires sufficiently large message sizes, smaller message sizes also desirable due to reduced implementation complexity and fewer constraints. By characterizing the capacity-achieving schemes, Tian, Sun, and Chen (2019) showed that the optimal message size for uniformly decomposable PIR schemes under no-collusion setting is $N-1$. However, comparable results are not yet available for more general collusion settings. In this work, we present a complete characterization of the properties of capacity-achieving decomposable PIR schemes under arbitrary collusion patterns. Building on this characterization, we derive a general lower bound on the optimal message size for capacity-achieving uniformly decomposable PIR schemes under an arbitrary collusion pattern $\mathcal{P}$, expressed in terms of the hitting number of a newly defined family of subsets of servers determined by the collusion pattern $\mathcal{P}$. Finally, we specialize the lower bound to several important classes of collusion patterns, including $T$-collusion, disjoint collections of colluding sets, cyclically $T$-contiguous collusion, and disjoint collections of cyclically contiguous colluding sets. For the last two collusion patterns, we present matching achievable schemes that attain the corresponding bounds, thereby providing a complete characterization of the optimal message size.

We design new minimal-subpacketization schemes for information-theoretic private information retrieval on graph-based replicated databases. In graph-based replication, the system consists of $K$ files replicated across $N$ servers according to a graph with $N$ vertices and $K$ edges. The client wants to retrieve one desired file, while keeping the index of the desired file private from each server via a query-response protocol. We seek PIR protocols that have (a) high rate, which is the ratio of the file-size to the total download cost, and (b) low subpacketization, which acts as a constraint on the size of the files for executing the protocol. We report two new schemes which have unit-subpacketization (which is minimal): (i) for a special class of graphs known as star graphs, and (ii) for general graphs. Our star-graph scheme has a better rate than previously known schemes with low subpacketization for general star graphs. Our scheme for general graphs uses a decomposition of the graph via independent sets. This scheme achieves a rate lower than prior schemes for the complete graph, however it can achieve higher rates than known for some specific graph classes. An extension of our scheme to the case of multigraphs achieves a higher rate than previous schemes for the complete multi-graph.

The problem of blind identification of channel codes at a receiver involves identifying a code chosen by a transmitter from a known code-family, by observing the transmitted codewords through the channel. Most existing approaches for code-identification are contingent upon the codes in the family having some special structure, and are often computationally expensive otherwise. Further, rigorous analytical guarantees on the performance of these existing techniques are largely absent. This work presents a new method for code-identification on the binary symmetric channel (BSC), inspired by the framework of subspace codes for operator channels, carefully combining principles of hamming-metric and subspace-metric decoding. We refer to this method as the minimum denoised subspace discrepancy decoder. We present theoretical guarantees for code-identification using this decoder, for bounded-weight errors, and also present a bound on the probability of error when used on the BSC. Simulations demonstrate the improved performance of our decoder for random linear codes beyond existing general-purpose techniques, across most channel conditions and even with a limited number of received vectors.

In pliable index coding (PICOD), a number of clients are connected via a noise-free broadcast channel to a server which has a list of messages. Each client has a unique subset of messages at the server as side-information, and requests for any one message not in the side-information. A PICOD scheme of length ℓ is a set of ℓ encoded transmissions broadcast from the server such that all clients are satisfied. Finding the optimal (minimum) length of PICOD and designing PICOD schemes that have small length are the fundamental questions in PICOD. In this paper, we use a hypergraph-based approach to derive new achievability and converse results for PICOD(t), where clients requesttnew messages (for somet≥ 1). We present a simple greedy algorithm for PICOD(1), termed DelGreedy, which gives an achievable linear scheme with length at most Δ(H), where Δ(H) is the maximum degree of any vertex in the hypergraphHthat represents the PICOD problem. We then extend this idea to obtain an achievable scheme for PICOD(t). We also give a lower bound for the optimal PICOD length using a new structural parameter associated with the PICOD hypergraph called the nesting number, denoted by η(H). While the nesting number bound is not stronger than previously known bounds, it can provide some computational advantages over them. Also, using the nesting number bound, we also obtain novel lower bounds for some PICOD problems with special structures, which are tight in some cases. We also characterize the optimal PICOD lengths for problems with Δ(H) ∈ {1, 2, 3}, and for problems with upto three clients. Further, we present a class of PICOD problems to show that the gap between the lower bound η(H) and the achievable PICOD length from DelGreedy algorithm can be arbitrarily large. Finally, we demonstrate the achievable PICOD lengths from our algorithms via simulations on randomly generated PICOD problems, and compare it with existing algorithms. We observe that DelGreedy performs better than some existing algorithms, while being worse than others, in terms of the code length achieved. Specifically, the greedy-cover based algorithm from a prior work of Brahma and Fragouli performs better, achieving lengths 1.5x-2x smaller than DelGreedy. However, the DelGreedy algorithm demonstrates 1.5x-3x faster running times than GRCOV, providing an alternative point in the rate-computation tradeoff of PICOD code design. These results extend to the PICOD(t) scenario also, with the improvements in computation-time over pre-existing algorithms being more dramatic in some cases.

In information-theoretic private information retrieval (PIR), a client wants to retrieve one desired file out of$M$files, stored across$N$servers, while keeping the index of the desired file private from each$T$-sized subset of servers. A PIR protocol must ideally maximize the rate, which is the ratio of the file size to the total quantum of the download from the servers, while ensuring such privacy. In Weak-PIR (WPIR), the criterion of perfect information-theoretic privacy is relaxed. This enables higher rates to be achieved, while some information about the desired file index leaks to the servers. This leakage is captured by various known privacy metrics. By leveraging the well-established capacity-achieving schemes of Sun and Jafar under non-colluding ($T=1$) and colluding ($1

The shotgun sequencing process involves fragmenting a long DNA sequence (input string) into numerous shorter, unordered, and overlapping segments (referred to as reads). The reads are sequenced, and later aligned to reconstruct the original string. Viewing the sequencing process as the read-phase of a DNA storage system, the information-theoretic capacity of noise-free shotgun sequencing has been characterized in literature. Motivated by the base-wise quality scores available in practical sequencers, a recent work considered the shotgun sequencing channel with erasures, in which the symbols in the reads are assumed to contain random erasures. Achievable rates for this channel were identified. In the present work, we obtain a converse for this channel. The arguments for the proof involve a careful analysis of a genie-aided decoder, which knows the correct locations of the reads. The converse is not tight in general. However, it meets the achievability result asymptotically in some channel parameters.

We introduce Berman-intersection-dual Berman (BiD) codes. These are abelian codes of length 3mthat can be constructed using Kronecker products of a 3×3 kernel matrix. BiD codes offer minimum distance close to that of Reed-Muller (RM) codes at practical blocklengths, and larger distance than RM codes asymptotically in the blocklength. Simulations of BiD codes of length 35= 243 in the erasure and Gaussian channels show that their block error rates under maximum-likelihood decoding are similar to, and sometimes better, than RM, RM-Polar, and CRC-aided Polar codes.

In shotgun sequencing, the input string (typically, a long DNA sequence composed of nucleotide bases) is sequenced as multiple overlapping fragments of much shorter lengths (called reads). Modelling the shotgun sequencing pipeline as a communication channel for DNA data storage, the capacity of this channel was identified in a recent work, assuming that the reads themselves are noiseless substrings of the original sequence. Modern shotgun sequencers however also output quality scores for each base read, indicating the confidence in its identification. Bases with low quality scores can be considered to be erased. Motivated by this, we consider the shotgun sequencing channel with erasures, where each symbol in any read can be independently erased with some probability$\delta$. We identify achievable rates for this channel, using a random code construction and a decoder that uses typicality-like arguments to merge the reads.

We study a family of subcodes of the$m-\mathbf{dimensional}$product code$\mathcal{C}^{\otimes m}$(‘subproduct codes’) that have a recursive Plotkin-like structure, and which include Reed-Muller (RM) codes and Dual Berman codes as special cases. We denote the codes in this family as$\mathcal{C}^{\otimes[r,m]}$, where$r\in\{0,1,\ \ldots,\ m\}$is the ‘order’ of the code. These codes allow a ‘projection’ operation that can be exploited in iterative decoding, viz., the sum of two carefully chosen subvectors of any codeword in$\mathcal{C}^{\otimes[r,m]}$belongs to$\mathcal{C}^{\otimes[r-1,m-1]}$. Recursive subproduct codes provide a wider range of rates and block lengths compared to RM codes while possessing several of their structural properties, such as the Plotkin-like design, the projection property, and fast ML decoding of first-order codes. Our simulation results for first-order and second-order codes, that are based on a belief propagation decoder and a local graph search algorithm, show instances of subproduct codes that perform either better than or within 0.5 dB of comparable RM codes and CRC-aided Polar codes.

We present a hypergraph coloring based approach to pliable index coding (PICOD). We represent the given PICOD problem using a hypergraph consisting ofmmessages as vertices and the request-sets of thenclients as hyperedges. Aconflict-free coloringof a hypergraph is an assignment of colors to its vertices so that each hyperedge contains a uniquely colored vertex. We show that various parameters arising out of conflict-free colorings (and some new variants) of the PICOD hypergraph result in new upper bounds for the optimal PICOD length. Using these new upper bounds, we show the existence of single-request PICOD schemes with lengthO(log2Γ), where Γ is the maximum number of hyperedges overlapping with any hyperedge. For thet-request PICOD scenario, we show the existence of PICOD schemes of length max(O(log Γ logm),O(tlogm)), under some mild conditions on the graph parameters. These results improve upon earlier work in general. We also show that our achievable lengths in thet-request case are asymptotically optimal, up to a multiplicative factor of logt. Our existence results are accompanied by randomized constructive algorithms, which have complexity polynomial in the parameters of the PICOD problem, in expectation or with high probability.

A code of length n is said to be (combinatorially) (ρ, L)-list decodable if the Hamming ball of radius ρn around any vector in the ambient space does not contain more than L codewords. We study a recently introduced class of higher order MDS codes, which are closely related (via duality) to codes that achieve a generalized Singleton bound for list decodability. For some ℓ ≥ 1, higher order MDS codes of length n, dimension k, and order ℓ are denoted as (n, k)-MDS(ℓ) codes. We present a number of results on the structure of these codes, identifying the ‘extend-ability’ of their parameters in various scenarios. Specifically, for some parameter regimes, we identify conditions under which (n1, k1)-MDS(ℓ1) codes can be obtained from (n2, k2)-MDS(ℓ2) codes, via various techniques. We believe that these results will aid in efficient constructions of higher order MDS codes. We also obtain a new field size upper bound for the existence of such codes, which arguably improves over the best known existing bound, in some parameter regimes.

We present a new class of private information retrieval (PIR) schemes that keep the identity of the file requested private in the presence of at most t colluding servers, based on the recent framework developed for such t-PIR schemes using star products of transitive codes. These t-PIR schemes employ the class of Berman codes as the storage-retrieval code pairs. Berman codes, which are binary linear codes of length nmfor any n ≥ 2 and m ≥ 1 being positive integers, were recently shown to achieve the capacity of the binary erasure channel. We provide a complete characterization of the star products of the Berman code pairs, enabling us to calculate the PIR rate of the star product-based schemes that employ these codes. The schemes we present have flexibility in the number of servers, the PIR rate, the storage rate, and the collusion parameter t, owing to numerous codes available in the class of Berman codes.Due to space restrictions, the full version of this paper containing proofs of claims, additional examples, and results, is made available in [1].

We study communication models for channels with erasures in which the erasure pattern can be controlled by an adversary with partial knowledge of the transmitted codeword. In particular, we design block codes for channels with binary inputs with an adversary who can erase a fraction p of the transmitted bits. We consider causal adversaries, who must choose to erase an input bit using knowledge of that bit and previously transmitted bits, and myopic adversaries, who can choose an erasure pattern based on observing the transmitted codeword through a binary erasure channel with random erasures. For both settings we design efficient (polynomial time) encoding and decoding algorithms that use randomization at the encoder only. Our constructions achieve capacity for the causal and "sufficiently myopic" models. For the "insufficiently myopic" adversary, the capacity is unknown, but existing converses show the capacity is zero for a range of parameters. For all parameters outside of that range, our construction achieves positive rates.

We identify a family of binary codes whose structure is similar to Reed-Muller (RM) codes and which include RM codes as a strict subclass. The codes in this family are denoted as$\mathscr {C}_{n}(r,m)$, and their duals are denoted as$\mathscr {B}_{n}(r,m)$. The length of these codes is$n^{m}$, where$n \geq 2$, and$r$is their ‘order’. When$n=2$,$\mathscr {C}_{n}(r,m)$is the RM code of order$r$and length$2^{m}$. The special case of these codes corresponding to$n$being an odd prime was studied by Berman (1967) and Blackmore and Norton (2001). Following the terminology introduced by Blackmore and Norton, we refer to$\mathscr {B}_{n}(r,m)$as the Berman code and$\mathscr {C}_{n}(r,m)$as the dual Berman code. We identify these codes using a recursive Plotkin-like construction, and we show that these codes have a rich automorphism group, they are generated by the minimum weight codewords, and that they can be decoded up to half the minimum distance efficiently. Using a result of Kumar et al. (2016), we show that these codes achieve the capacity of the binary erasure channel (BEC) under bit-MAP decoding. Furthermore, except double transitivity, they satisfy all the code properties used by Reeves and Pfister to show that RM codes achieve the capacity of binary-input memoryless symmetric channels. Finally, when$n$is odd, we identify a large class of abelian codes that includes$\mathscr {B}_{n}(r,m)$and$\mathscr {C}_{n}(r,m)$and which achieves BEC capacity.

We identify a family of binary codes whose structure is similar to Reed-Muller (RM) codes and which include RM codes as a strict subclass. The codes in this family are denoted as ${\mathcal{C}_n}(r,m)$, and their duals are denoted as ${{\mathcal{B}}_n}(r,m)$. The length of these codes is nm, where n ≥ 2, and r is their ‘order’. When n = 2, ${\mathcal{C}_n}(r,m)$ is the RM code of order r and length 2m. The special case of these codes corresponding to n being an odd prime was studied by Berman (1967) and Blackmore and Norton (2001). Following the terminology introduced by Blackmore and Norton, we refer to ${{\mathcal{B}}_n}(r,m)$ as the Berman code and ${\mathcal{C}_n}(r,m)$ as the dual Berman code. We identify these codes using a recursive Plotkin-like construction, and we show that these codes have a rich automorphism group. Applying a result of Kumar et al. (2016) to this set of automorphisms, we show that these codes achieve the capacity of the binary erasure channel (BEC) under bit-MAP decoding.

In pliable index coding (PICOD), a number of clients are connected via a noise-free broadcast channel to a server which has a list of messages. Each client has a unique subset of messages at the server as side-information and requests for any one message not in the side-information. A PICOD scheme of length ℓ is a set of ℓ encoded transmissions broadcast from the server such that all clients are satisfied. Finding the optimal (minimum) length of PICOD and designing PICOD schemes that have small length are the fundamental questions in PICOD. In this paper, we use a hypergraph-based approach to derive new achievability and converse results for PICOD. We present an algorithm which gives an achievable scheme for PICOD with length at most $\Delta \left( \mathcal{H} \right)$, where $\Delta \left( \mathcal{H} \right)$ is the maximum degree of any vertex in a hypergraph that represents the PICOD problem. We also give a lower bound for the optimal PICOD length using a new structural parameter associated with the PICOD hypergraph called the nesting number. Finally, we also identify a class of problems for which our converse is tight. The full version of this paper, including additional results, proofs, and examples, is available online [1].

We consider replication-based distributed storage systems in which each node stores the same quantum of data and each data bit stored has the same replication factor across the nodes. Such systems are referred to as balanced distributed databases. When existing nodes leave or new nodes are added to this system, the balanced nature of the database is lost, either due to the reduction in the replication factor, or the non-uniformity of the storage at the nodes. This triggers a rebalancing algorithm, that exchanges data between the nodes so that the balance of the database is reinstated. The goal is then to design rebalancing schemes with minimal communication load. In a recent work by Krishnan et al., coded transmissions were used to rebalance a carefully designed distributed database from a node removal or addition. These coded rebalancing schemes have optimal communication load, however, require the file-size to be at least exponential in the system parameters. In this work, we consider a cyclic balanced database (where data is cyclically placed in the system nodes) and present coded rebalancing schemes for node removal and addition in such a database. These databases (and the associated rebalancing schemes) require the file-size to be only cubic in the number of nodes in the system. We bound the advantage of our node removal rebalancing scheme over the uncoded scheme, and show that our scheme has a smaller communication load. In the node addition scenario, the rebalancing scheme presented is a simple uncoded scheme, which we show has optimal load.Due to space restrictions, the current version of this paper contains only a subset of the results concerning the node removal scenario. The full version of this paper, including additional results and examples, is available online [1].

In the pliable index coding (PICOD) problem, a server is to serve multiple clients, each of which possesses a unique subset of the complete message set as side information and requests a new message which it does not have. The goal of the server is to do this using as few transmissions as possible. This work presents a hypergraph coloring approach to the PICOD problem. A conflict-free coloring of a hypergraph is known from literature as an assignment of colors to its vertices so that each edge of the graph contains one uniquely colored vertex. For a given PICOD problem represented by a hypergraph consisting of messages as vertices and request-sets as edges, we present achievable PICOD schemes using conflict-free colorings of the PICOD hypergraph. Various graph theoretic parameters arising out of such colorings (and some new coloring variants) then give a number of upper bounds on the optimal PICOD length, which we study in this work. Our achievable schemes based on hypergraph coloring include scalar as well as vector linear PICOD schemes. For the scalar case, using the correspondence with conflict-free coloring, we show the existence of an achievable scheme which has length$O(\log^{2}\Gamma)$, where$\Gamma$refers to a parameter of the hypergraph that captures the maximum ‘incidence’ number of other edges on any edge. This result improves upon known achievability results in PICOD literature, in some parameter regimes.

Large gains in the rate of cache-aided broadcast communication are obtained using coded caching, but to obtain this most existing centralized coded caching schemes require that the files at the server be divisible into a large number of parts (this number is called subpacketization). In fact, most schemes require the subpacketization to be growing asymptotically as exponential in √[\leftroot -1\uproot 1r]K for some positive integer r and K being the number of users. On the other extreme, few schemes having subpacketization linear in K are known; however, they require large number of users to exist, or they offer only little gain in the rate. In this work, we propose two new centralized coded caching schemes with low subpacketization and moderate rate gains utilizing projective geometries over finite fields. Both the schemes achieve the same asymptotic subpacketization, which is exponential in O((logK)2) (thus improving on the √[\leftroot -1\uproot 1r]K exponent). The first scheme has a larger cache requirement but has at most a constant rate (with increasing K), while the second has small cache requirement but has a larger rate. As a special case of our second scheme, we get a new linear subpacketization scheme, which has a more flexible range of parameters than the existing linear subpacketization schemes. Extending our techniques, we also obtain low subpacketization schemes for other multi-receiver settings such as distributed computing and the cache-aided interference channel. We validate the performance of all our schemes via extensive numerical comparisons. For a special class of symmetric caching schemes with a given subpacketization level, we propose two new information theoretic lower bounds on the optimal rate of coded caching.

We consider the distributed computing framework of MapReduce, which consists of three phases, the Map phase, the Shuffle phase and the Reduce phase. For this framework, we propose the use of binary matrices (with 0,1 entries) called computing matrices to describe the map phase and the shuffle phase. Similar binary matrices were recently proposed for the coded caching framework. The structure of ones and zeroes in the binary computing matrix captures the map phase of the MapReduce framework. We present a new simple coded data shuffling scheme for this binary matrix model, based on a identity submatrix cover of the computing matrix. This new coded shuffling scheme has in general a larger communication load than existing schemes, but has the advantage of less complexity overhead than the well-known earlier schemes in literature in terms of the file-splitting and associated indexing and coordination required. We also show that there exists a binary matrix based distributed computing scheme with our new data-shuffling scheme which has strictly less than twice than the communication load of the known optimal scheme in literature. The structure of this new scheme enables it to be applied to the framework of MapReduce with stragglers also, in a straightforward manner, borrowing its advantages and disadvantages from the no-straggler situation. Finally, using binary matrices derived from combinatorial designs, we show specific classes of computing schemes with very low file complexity (number of subfiles in the file), with marginally higher communication load compared to the optimal scheme for equivalent parameters.

Distributed databases often suffer unequal distribution of data among storage nodes, which is known as `data skew'. Data skew arises from a number of causes such as removal of existing storage nodes and addition of new empty nodes to the database. Data skew leads to performance degradations and thus necessitates `rebalancing' at regular intervals to reduce the amount of skew. We define an r-balanced distributed database as a distributed database in which the storage across the nodes has uniform size, and each bit of the data is replicated in r distinct storage nodes. We consider the problem of designing such balanced databases along with associated rebalancing schemes which maintain the r-balanced property under node removal and addition operations. We present a class of r-balanced databases (parameterized by the number of storage nodes) which have the property of structural invariance, i.e., the databases designed for different number of storage nodes have the same structure. For this class of r-balanced databases, we present rebalancing schemes which use coded transmissions between storage nodes, and characterize their communication loads under node addition and removal. We show that the communication cost incurred to rebalance our distributed database for node addition and removal is optimal, i.e., it achieves the minimum possible cost among all possible balanced distributed databases and rebalancing schemes.

We consider the centralized coded caching system where a library of files is available at the server and their subfiles are cached at the clients as prescribed by a placement delivery array (PDA). We are interested in the problem where a specific file in the library is replaced with a new file at the server, the contents of which are correlated with the file being replaced, and this replacement needs to be communicated to the caches. The server loses the original file when the replacement is done and is unaware of the differences between the two files, whereas each cache has access to specific subfiles of the original file as dictated by the PDA. We model the correlation between the two files by assuming that they differ in at the most subfiles, and aim to reduce the number of bits broadcast by the server to update the caches. We design a new elegant coded transmission strategy for the server to update the caches blindly, and also identify another simple scheme that is based on MDS codes. We then derive converse bounds on the minimum cost ℓ*among all linear strategies. For two well-known families of PDAs – the Maddah-Ali-Niesen scheme and a scheme by Tang & Ramamoorthy and Yan et al. – we show that our new scheme has cost ℓ*(1 + o(1)) when the updates are sufficiently sparse, while the scheme using MDS codes has order-optimal cost when the updates are dense.

The problem of data exchange between multiple nodes with (not necessarily uniform) storage and communication capabilities models several current multi-user communication problems like Coded Caching, Data shuffling, Coded Computing, etc. The goal in such problems is to design communication schemes which accomplish the desired data exchange between the nodes with the optimal (minimum) amount of communication load. In this work, we present a converse to such a general data exchange problem between multiple nodes. The expression of the converse depends only on the number of bits to be moved between different subsets of nodes, and does not assume anything further specific about the parameters in the problem. Specific problem formulations, such as those in Coded Caching, Coded Data Shuffling, Coded Distributed Computing, and some of their variants, naturally can be seen as instances of this generic data exchange problem. Applying our generic converse to such problems, we recover known important converses for these settings and some of their variants in a simpler way. Further, for a generic coded caching problem with multiple transmitters, receivers and cache sizes, we show a new general converse which subsumes many existing results. We also employ our bound to obtain a new tight converse bound for the multi-node removal case in the Coded Data Rebalancing problem, in which nodes must exchange information to ‘rebalance’ a storage cluster after some node failures occur.Due to space restrictions, the full version of this paper, containing proofs and additional results, is made available in [1].

The performance of replication-based distributed databases is affected due to non-uniform storage across storage nodes (also called data skew) and reduction in the replication factor during operation, particularly due to node additions or removals. Data rebalancing refers to the communication involved between the nodes in correcting this data skew, while maintaining the replication factor. For carefully designed distributed databases, transmitting coded symbols during the rebalancing phase has been recently shown to reduce the communication load of rebalancing. In this work, we look at balanced distributed databases with random placement, in which each data segment is stored in a random subset of r nodes in the system, where r refers to the replication factor of the distributed database. We call these as decentralized databases. For a natural class of such decentralized databases, we propose rebalancing schemes for correcting data skew and the reduction in the replication factor arising due to a single node addition or removal. We give converse arguments which show that our proposed rebalancing schemes are optimal asymptotically in the size of the file.Due to space restrictions, the full version of this paper, containing proofs and additional results, is made available in [1].

An index code for broadcast channel with receiver side information is locally decodable if each receiver can decode its demand by observing only a subset of the transmitted codeword symbols instead of the entire codeword. Local decodability in index coding is known to reduce receiver complexity, improve user privacy and decrease decoding error probability in wireless fading channels. Conventional index coding solutions assume that the receivers observe the entire codeword, and as a result, for these codes the number of codeword symbols queried by a user per decoded message symbol, which we refer to as locality, could be large. In this paper, we pose the index coding problem as that of minimizing the broadcast rate for a given value of locality (or vice versa) and designing codes that achieve the optimal trade-off between locality and rate. We identify the optimal broadcast rate corresponding to the minimum possible value of locality for all single unicast problems. We present new structural properties of index codes which allow us to characterize the optimal trade-off achieved by: vector linear codes when the side information graph is a directed cycle; and scalar linear codes when the minrank of the side information graph is one less than the order of the problem. We also identify the optimal trade-off among all codes, including non-linear codes, when the side information graph is a directed 3-cycle. Finally, we present techniques to design locally decodable index codes for arbitrary single unicast problems and arbitrary values of locality.

Coded caching was introduced as a technique of systematically exploiting locally available storage at the clients to increase the channel throughput via coded transmissions. Most known coded caching schemes in literature enable large gains in terms of the rate, however at the cost of subpacketization that is exponential in K1/r(K being the number of clients, r some positive integer). Building upon recent prior work for coded caching design via line graphs and finite-field projective geometries, we present a new scheme in this work which achieves a subexponential (in K) subpacketization of qO((log(q) K)2)rate ⊖ (K/log(q) K)2) , for large K, and the cached fraction M/N being upper bounded by a constant 2/qα-1(for some prime power q and constant α ≥ 2). Apart from this asymptotic improvement, we show that through some numerical comparisons that our present scheme has much lower subpacketization than previous comparable schemes, however with an increased rate and some increase in cache size required. For instance, we obtain practically relevant subpacketization levels such as 102-107-for 102-104number of clients. Leveraging prior results on adapting coded caching schemes for the error-free broadcast channel to device to device (D2D) networks, we obtain a low-subpacketization scheme for D2D networks also, and give numerical comparison for the same with prior work.

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.

We consider the standard broadcast setup with a single server broadcasting information to a number of clients, each of which contains local storage (called cache) of some size, which can store some parts of the available files at the server. The centralized coded caching framework, consists of a caching phase and a delivery phase, both of which are carefully designed in order to use the cache and the channel together optimally. In prior literature, various combinatorial structures have been used to construct coded caching schemes. In this work, we propose a binary matrix model to construct the coded caching scheme. The ones in such a caching matrix indicate uncached subfiles at the users. Identity submatrices of the caching matrix represent transmissions in the delivery phase. Using this model, we then propose several novel constructions for coded caching based on the various types of combinatorial designs. While most of the schemes constructed in this work (based on existing designs) have a high cache requirement (uncached fraction being Θ( √1K), K being the number of users), they provide a rate R that is upper bounded by a constant (R ≤ 1) with increasing K, and moreover require extremely small levels of subpacketization (being O(K)), which is an extremely important parameter in practical applications of coded caching.

Circular perfect graphs are those undirected graphs such that the circular clique number is equal to the circular chromatic number for each induced subgraph. They form a strict superclass of the perfect graphs, whose index coding broadcast rates are well known. We present the broadcast rate of index coding for side-information graphs whose complements are circular perfect, along with an optimal achievable scheme. We thus enlarge the known classes of graphs for which the broadcast rate is exactly characterized. In an attempt to understand the broadcast rate of a graph given that of its complement, we obtain upper and lower bounds for the product and sum of the vector linear broadcast rates of a graph and its complement. We show that these bounds are satisfied with equality even for some perfect graphs. Curating prior results, we show that there are circular perfect but imperfect graphs which satisfy the lower bound on the product of the broadcast rate of the complementary graphs with equality.

Coded Caching is a promising solution to reduce the peak traffic in broadcast networks by prefetching the popular content close to end users and using coded transmissions. One of the chief issues of most coded caching schemes in literature is the issue of large subpacketization, i.e., they require each file to be divided into a large number of subfiles. In this work, we present a coded caching scheme using line graphs of bipartite graphs in conjunction with projective geometries over finite fields. The presented scheme achieves a rate Θ(K/logqK) (K being the number of users, q is some prime power) with subexponential subpacketization qO((logq K)^2)when cached fraction is upper bounded by a constant (M/N ≤ 1/qα, for some positive integer α). Compared to earlier schemes, the presented scheme has a lower subpacketization (albeit possessing a higher rate). We also present a new subpacketization dependent lower bound on the rate for caching schemes in which each subfile is cached in the same number of users. Compared to the previously known bounds, this bound seems to perform better for a range of parameters of the caching system.

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 coding scheme based on fractional coloring of the interference graph is optimal for this locality. We then propose index coding schemes with small locality by covering the side information graph using acyclic subgraphs and subgraphs of small minrank. We also show how locality can be accounted for in conventional partition multicast and cycle covering solutions to index coding, thereby yielding locally decodable index codes.

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 qO((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.

Linear index coding can be formulated as an interference alignment problem, in which precoding vectors of the minimum possible length are to be assigned to the messages in such a way that the precoding vector of a demand (at some receiver) is independent of the space of the interference (non side-information) precoding vectors. An index code has rate 1/l if the assigned vectors are of length l. In this paper, we introduce the notion of strictly rate 1/L message subsets which must necessarily be allocated precoding vectors from a strictly L-dimensional space (L = 1, 2, 3) in any rate 1/3 code. We develop a general necessary condition for rate 1/3 feasibility using intersections of strictly rate 1/L message subsets. We apply the necessary condition to show that the presence of certain interference configurations makes the index coding problem rate 1/3 infeasible. We also obtain a class of index coding problems, containing certain interference configurations, which are rate 1/3 feasible based on the idea of contractions of an index coding problem. Our necessary conditions for rate 1/3 feasibility and the class of rate 1/3 feasible problems obtained subsume all such known results for rate 1/3 index coding.

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 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.

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 users during 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 on exploiting the presence of common demands between multiple users.

An index coding problem with n 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 rate 1/3 is 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 rate 1/3 is achievable. In the process, we also obtain a stricter necessary condition for rate 1/3 feasibility than what is known in literature.

Matroidal networks were introduced by Dougherty et 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 network abstracting 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 multisource, 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 multicast 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, whereas there are no linear network-error detecting codes that do the same.

Existing construction algorithms of block network-error correcting codes require a rather large field size, which grows with the size of the network and the number of sinks, and thereby can be prohibitive in large networks. In this work, we give an algorithm which, starting from a given network-error correcting code, can obtain another network code using a small field, with the same error correcting capability as the original code. An algorithm for designing network codes using small field sizes proposed recently by Ebrahimi and Fragouli can be seen as a special case of our algorithm. The major step in our algorithm is to find a least degree irreducible polynomial which is coprime to another large degree polynomial. We utilize the algebraic properties of finite fields to implement this step so that it becomes much faster than the brute-force method. As a result the algorithm given by Ebrahimi and Fragouli is also quickened.

The algebraic formulation for linear network coding in acyclic networks with the links having integer delay is well known. Based on this formulation, for a given set of connections over an arbitrary acyclic network with integer delay assumed for the links, the output symbols at the sink nodes, at any given time instant, is a Fpm-linear combination of the input symbols across different generations, where Fpm denotes the field over which the network operates (p is prime and m is a positive integer). We use finite-field discrete Fourier transform to convert the output symbols at the sink nodes, at any given time instant, into a Fpm-linear combination of the input symbols generated during the same generation without making use of memory at the intermediate nodes. We call this as transforming the acyclic network with delay into n-instantaneous networks (n is sufficiently large). We show that under certain conditions, there exists a network code satisfying sink demands in the usual (nontransform) approach if and only if there exists a network code satisfying sink demands in the transform approach. When the zero-interference conditions are not satisfied, we propose three precoding-based network alignment (PBNA) schemes for three-source three-destination multiple unicast network with delays (3-S 3-D MUN-D) termed as PBNA using transform approach and time-invariant local encoding coefficients (LECs), PBNA using time-varying LECs, and PBNA using transform approach and block time-varying LECs. We derive sets of necessary and sufficient conditions under which throughputs close to n' + 1/2n' + 1, n'/2n'+ 1, and n'/2n'+ 1 are achieved for the three source-destination pairs in a 3-S 3-D MUN-D employing PBNA using transform approach and time-invariant LECs, and PBNA using transform approach and block time-varying LECs, where n' is a positive integer. For PBNA using time-varying LECs, we obtain a sufficient condition under which a throughput demand of n1/n, n2/n, and n3/n can be met for the three source-destination pairs in a 3-S 3-D MUN-D, where n1, n2, and n3are positive integers less than orequal to the positive integer n. This condition is also necessary when n1+ n3= n1+ n2= n where n1≥ n2≥ n3.

The algebraic formulation for linear network coding in acyclic networks with each link having an integer delay is well known. Based on this formulation, for a given set of connections over an arbitrary acyclic network with integer delay assumed for the links, the output symbols at the sink nodes at any given time instant is a Fq-linear combination of the input symbols across different generations, where Fqdenotes the field over which the network operates. We use finite-field discrete Fourier transform (DFT) to convert the output symbols at the sink nodes at any given time instant into a Fq-linear combination of the input symbols generated during the same generation. We call this as transforming the acyclic network with delay into n-instantaneous networks (n is sufficiently large). We show that under certain conditions, there exists a network code satisfying sink demands in the usual (non-transform) approach if and only if there exists a network code satisfying sink demands in the transform approach. Furthermore, assuming time invariant local encoding kernels, we show that the transform method can be employed to achieve half the rate corresponding to the individual source-destination mincut (which are assumed to be equal to 1) for some classes of three-source three-destination multiple unicast network with delays using alignment strategies when the zero-interference condition is not satisfied.

Matroidal networks were introduced by Dougherty et 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. The current work attempts to establish a connection between matroid theory and network-error correcting codes. In a similar vein to the theory connecting matroids and network coding, we abstract the essential aspects of network-error correcting codes to arrive at the definition of a matroidal error correcting network. An acyclic network (with arbitrary sink demands) is then shown to possess a scalar linear error correcting network code if and only if it is a matroidal error correcting network associated with a representable matroid. Therefore, constructing such network-error correcting codes implies the construction of certain representable matroids that satisfy some special conditions, and vice versa.

Recently, Ebrahimi and Fragouli proposed an algorithm to construct scalar network codes using small fields (and vector network codes of small lengths) satisfying multicast constraints in a given single-source, acyclic network. The contribution of this paper is two fold. Primarily, we extend the scalar network coding algorithm of Ebrahimi and Fragouli (henceforth referred to as the EF algorithm) to block network-error correction. Existing construction algorithms of block network-error correcting codes require a rather large field size, which grows with the size of the network and the number of sinks, and thereby can be prohibitive in large networks. We give an algorithm which, starting from a given network-error correcting code, can obtain another network code using a small field, with the same error correcting capability as the original code. Our secondary contribution is to improve the EF Algorithm itself. The major step in the EF algorithm is to find a least degree irreducible polynomial which is coprime to another large degree polynomial. We suggest an alternate method to compute this coprime polynomial, which is faster than the brute force method in the work of Ebrahimi and Fragouli.

The concept of interference alignment when extended to three-source three-destination instantaneous multiple unicast network for the case where, each source-destination pair has a min-cut of 1 and zero-interference conditions are not satisfied, is known to achieve a rate of half for every source-destination pair under certain conditions. This was called network alignment. We generalize this concept of network alignment to three-source three-destination multiple unicast (3S-3D-MU) networks with delays, without making use of memory at the intermediate nodes (i.e., nodes other than the sources and destinations) and using time varying Local Encoding Kernels (LEKs). This achieves half the rate corresponding to the individual source-destination min-cut for some classes of 3S-3D-MU network with delays which do not satisfy the zero-interference conditions.

Problems related to network coding for acyclic, instantaneous networks (where the edges of the acyclic graph representing the network are assumed to have zero-delay) have been extensively dealt with in the recent past. The most prominent of these problems include (a) the existence of network codes that achieve maximum rate of transmission, (b) efficient network code constructions, and (c) field size issues. In practice, however, networks have transmission delays. In network coding theory, such networks with transmission delays are generally abstracted by assuming that their edges have integer delays. Using enough memory at the nodes of an acyclic network with integer delays can effectively simulate instantaneous behavior, which is probably why only acyclic instantaneous networks have been primarily focused on thus far. However, nulling the effect of the network delays are not always uniformly advantageous, as we will show in this work. Essentially, we elaborate on issues ((a), (b) and (c) above) related to network coding for acyclic networks with integer delays, and show that using the delay network as is (without adding memory) turns out to be advantageous, disadvantageous or immaterial, depending on the topology of the network and the problem considered i.e., (a), (b) or (c).

A single source network is said to be memory-free if all of the internal nodes (those except the source and the sinks) do not employ memory but merely send linear combinations of the symbols received at their incoming edges on their outgoing edges. In this work, we introduce network-error correction for single source, acyclic, unit-delay, memory-free networks with coherent network coding for multicast. A convolutional code is designed at the source based on the network code in order to correct network- errors that correspond to any of a given set of error patterns, as long as consecutive errors are separated by a certain interval which depends on the convolutional code selected. Bounds on this interval and the field size required for constructing the convolutional code with the required free distance are also obtained. We illustrate the performance of convolutional network error correcting codes (CNECCs) designed for the unit-delay networks using simulations of CNECCs on an example network under a probabilistic error model.

A single-source network is said to be memory-free if all of the internal nodes (those except the source and the sinks) do not employ memory but merely send linear combinations of the incoming symbols (received at their incoming edges) on their outgoing edges. Memory-free networks with delay using network coding are forced to do inter-generation network coding, as a result of which the problem of some or all sinks requiring a large amount of memory for decoding is faced. In this work, we address this problem by utilizing memory elements at the internal nodes of the network also, which results in the reduction of the number of memory elements used at the sinks. We give an algorithm which employs memory at all the nodes of the network to achieve single- generation network coding. For fixed latency, our algorithm reduces the total number of memory elements used in the network to achieve single- generation network coding. We also discuss the advantages of employing single-generation network coding together with convolutional network-error correction codes (CNECCs) for networks with unit- delay and illustrate the performance gain of CNECCs by using memory at the intermediate nodes using simulations on an example network under a probabilistic network error model.

Convolutional network-error correcting codes (CNECCs) are known to provide error correcting capability in acyclic instantaneous networks within the network coding paradigm under small field size conditions. In this work, we investigate the performance of CNECCs under the error model of the network where the edges are assumed to be statistically independent binary symmetric channels, each with the same probability of error pe(0 ≤ peeshould be so that only single edge network-errors need to be accounted for, thus reducing the complexity of evaluating the probability of error of any CNECC. Simulations indicate that convolutional codes are required to possess different properties to achieve good performance in low peand high peregimes. For the low peregime, convolutional codes with good distance properties show good performance. For the high peregime, convolutional codes that have a good slope (the minimum normalized cycle weight) are seen to be good. We derive a lower bound on the slope of any rate b/c convolutional code with a certain degree.

In this work, we introduce convolutional codes for network-error correction in the context of coherent network coding. We give a construction of convolutional codes that correct a given set of error patterns, as long as consecutive errors are separated by a certain interval. We also give some bounds on the field size and the number of errors that can get corrected in a certain interval. Compared to previous network error correction schemes, using convolutional codes is seen to have advantages in field size and decoding technique. Some examples are discussed which illustrate the several possible situations that arise in this context.