Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userLocal Partial Clique Covers for Index Coding
94
0
0.0
(
0
)
Added by
Arya Mazumdar
Publication date
2016
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
Index coding, or broadcasting with side information, is a network coding problem of most fundamental importance. In this problem, given a directed graph, each vertex represents a user with a need of information, and the neighborhood of each vertex represents the side information availability to that user. The aim is to find an encoding to minimum number of bits (optimal rate) that, when broadcasted, will be sufficient to the need of every user. Not only the optimal rate is intractable, but it is also very hard to characterize with some other well-studied graph parameter or with a simpler formulation, such as a linear program. Recently there have been a series of works that address this question and provide explicit schemes for index coding as the optimal value of a linear program with rate given by well-studied properties such as local chromatic number or partial clique-covering number. There has been a recent attempt to combine these existing notions of local chromatic number and partial clique covering into a unified notion denoted as the local partial clique cover (Arbabjolfaei and Kim, 2014). We present a generalized novel upper-bound (encoding scheme) - in the form of the minimum value of a linear program - for optimal index coding. Our bound also combines the notions of local chromatic number and partial clique covering into a new definition of the local partial clique cover, which outperforms both the previous bounds, as well as beats the previous attempt to combination. Further, we look at the upper bound derived recently by Thapa et al., 2015, and extend their $n$-$mathsf{GIC}$ (Generalized Interlinked Cycle) construction to $(k,n)$-$mathsf{GIC}$ graphs, which are a generalization of $k$-partial cliques.
rate research
Read More
We study the fundamental problem of index coding under an additional privacy constraint that requires each receiver to learn nothing more about the collection of messages beyond its demanded messages from the server and what is available to it as side information. To enable such private communication, we allow the use of a collection of independent secret keys, each of which is shared amongst a subset of users and is known to the server. The goal is to study properties of the key access structures which make the problem feasible and then design encoding and decoding schemes efficient in the size of the server transmission as well as the sizes of the secret keys. We call this the private index coding problem. We begin by characterizing the key access structures that make private index coding feasible. We also give conditions to check if a given linear scheme is a valid private index code. For up to three users, we characterize the rate region of feasible server transmission and key rates, and show that all feasible rates can be achieved using scalar linear coding and time sharing; we also show that scalar linear codes are sub-optimal for four receivers. The outer bounds used in the case of three users are extended to arbitrary number of users and seen as a generalized version of the well-known polymatroidal bounds for the standard non-private index coding. We also show that the presence of common randomness and private randomness does not change the rate region. Furthermore, we study the case where no keys are shared among the users and provide some necessary and sufficient conditions for feasibility in this setting under a weaker notion of privacy. If the server has the ability to multicast to any subset of users, we demonstrate how this flexibility can be used to provide privacy and characterize the minimum number of server multicasts required.
We study the index coding problem in the presence of an eavesdropper, where the aim is to communicate without allowing the eavesdropper to learn any single message aside from the messages it may already know as side information. We establish an outer bound on the underlying secure capacity region of the index coding problem, which includes polymatroidal and security constraints, as well as the set of additional decoding constraints for legitimate receivers. We then propose a secure variant of the composite coding scheme, which yields an inner bound on the secure capacity region of the index coding problem. For the achievability of secure composite coding, a secret key with vanishingly small rate may be needed to ensure that each legitimate receiver who wants the same message as the eavesdropper, knows at least two more messages than the eavesdropper. For all securely feasible index coding problems with four or fewer messages, our numerical results establish the secure index coding capacity region.
We investigate the construction of weakly-secure index codes for a sender to send messages to multiple receivers with side information in the presence of an eavesdropper. We derive a sufficient and necessary condition for the existence of index codes that are secure against an eavesdropper with access to any subset of messages of cardinality $t$, for any fixed $t$. In contrast to the benefits of using random keys in secure network coding, we prove that random keys do not promote security in three classes of index-coding instances.
This letter investigates a new class of index coding problems. One sender broadcasts packets to multiple users, each desiring a subset, by exploiting prior knowledge of linear combinations of packets. We refer to this class of problems as index coding with coded side-information. Our aim is to characterize the minimum index code length that the sender needs to transmit to simultaneously satisfy all user requests. We show that the optimal binary vector index code length is equal to the minimum rank (minrank) of a matrix whose elements consist of the sets of desired packet indices and side- information encoding matrices. This is the natural extension of matrix minrank in the presence of coded side information. Using the derived expression, we propose a greedy randomized algorithm to minimize the rank of the derived matrix.
Index coding is a source coding problem in which a broadcaster seeks to meet the different demands of several users, each of whom is assumed to have some prior information on the data held by the sender. If the sender knows its clients requests and their side-information sets, then the number of packet transmissions required to satisfy all users demands can be greatly reduced if the data is encoded before sending. The collection of side-information indices as well as the indices of the requested data is described as an instance of the index coding with side-information (ICSI) problem. The encoding function is called the index code of the instance, and the number of transmissions employed by the code is referred to as its length. The main ICSI problem is to determine the optimal length of an index code for and instance. As this number is hard to compute, bounds approximating it are sought, as are algorithms to compute efficient index codes. Two interesting generalizations of the problem that have appeared in the literature are the subject of this work. The first of these is the case of index coding with coded side information, in which linear combinations of the source data are both requested by and held as users side-information. The second is the introduction of error-correction in the problem, in which the broadcast channel is subject to noise. In this paper we characterize the optimal length of a scalar or vector linear index code with coded side information (ICCSI) over a finite field in terms of a generalized min-rank and give bounds on this number based on constructions of random codes for an arbitrary instance. We furthermore consider the length of an optimal error correcting code for an instance of the ICCSI problem and obtain bounds on this number, both for the Hamming metric and for rank-metric errors. We describe decoding algorithms for both categories of errors.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
