Search

In this paper we study the data exchange problem where a set of users is interested in gaining access to a common file, but where each has only partial knowledge about it as side-information. Assuming that the file is broken into packets, the side-information considered is in the form of linear combinations of the file packets. Given that the collective information of all the users is sufficient to allow recovery of the entire file, the goal is for each user to gain access to the file while minimizing some communication cost. We assume that users can communicate over a noiseless broadcast channel, and that the communication cost is a sum of each user's cost function over the number of bits it transmits. For instance, the communication cost could simply be the total number of bits that needs to be transmitted. In the most general case studied in this paper, each user can have any arbitrary convex cost function. We provide deterministic, polynomial-time algorithms (in the number of users and packets) which find an optimal communication scheme that minimizes the communication cost. To further lower the complexity, we also propose a simple randomized algorithm inspired by our deterministic algorithm which is based on a random linear network coding scheme., Comment: submitted to Transactions on Information Theory

In this paper we study the multisource multicast problem where every sink in a given directed acyclic graph is a client and is interested in a common file. We consider the case where each node can have partial knowledge about the file as a side information. Assuming that nodes can communicate over the capacity constrained links of the graph, the goal is for each client to gain access to the file, while minimizing some linear cost function of number of bits transmitted in the network. We consider three types of side-information settings:(ii) side information in the form of linearly correlated packets; and (iii) the general setting where the side information at the nodes have an arbitrary (i.i.d.) correlation structure. In this work we 1) provide a polynomial time feasibility test, i.e., whether or not all the clients can recover the file, and 2) we provide a polynomial-time algorithm that finds the optimal rate allocation among the links of the graph, and then determines an explicit transmission scheme for cases (i) and (ii).

In this paper we construct a deterministic polynomial time algorithm for the problem where a set of users is interested in gaining access to a common file, but where each has only partial knowledge of the file. We further assume the existence of another set of terminals in the system, called helpers, who are not interested in the common file, but who are willing to help the users. Given that the collective information of all the terminals is sufficient to allow recovery of the entire file, the goal is to minimize the (weighted) sum of bits that these terminals need to exchange over a noiseless public channel in order achieve this goal. Based on established connections to the multi-terminal secrecy problem, our algorithm also implies a polynomial-time method for constructing the largest shared secret key in the presence of an eavesdropper. We consider the following side-information settings: (i) side-information in the form of uncoded packets of the file, where the terminals' side-information consists of subsets of the file; (ii) side-information in the form of linearly correlated packets, where the terminals have access to linear combinations of the file packets; and (iii) the general setting where the the terminals' side-information has an arbitrary (i.i.d.) correlation structure. We provide a polynomial-time algorithm (in the number of terminals) that finds the optimal rate allocations for these terminals, and then determines an explicit optimal transmission scheme for cases (i) and (ii).

We study the problem of constructing a deterministic polynomial time algorithm that achieves omniscience, in a rate-optimal manner, among a set of users that are interested in a common file but each has only partial knowledge about it as side-information. Assuming that the collective information among all the users is sufficient to allow the reconstruction of the entire file, the goal is to minimize the (possibly weighted) amount of bits that these users need to exchange over a noiseless public channel in order for all of them to learn the entire file. Using established connections to the multi-terminal secrecy problem, our algorithm also implies a polynomial-time method for constructing a maximum size secret shared key in the presence of an eavesdropper. We consider the following types of side-information settings: (i) side information in the form of uncoded fragments/packets of the file, where the users' side-information consists of subsets of the file; (ii) side information in the form of linearly correlated packets, where the users have access to linear combinations of the file packets; and (iii) the general setting where the the users' side-information has an arbitrary (i.i.d.) correlation structure. Building on results from combinatorial optimization, we provide a polynomial-time algorithm (in the number of users) that, first finds the optimal rate allocations among these users, then determines an explicit transmission scheme (i.e., a description of which user should transmit what information) for cases (i) and (ii).

A multiplicative Gaussian wire-tap channel inspired by compressed sensing is studied. Lower and upper bounds on the secrecy capacity are derived, and shown to be relatively tight in the large system limit for a large class of compressed sensing matrices. Surprisingly, it is shown that the secrecy capacity of this channel is nearly equal to the capacity without any secrecy constraint provided that the channel of the eavesdropper is strictly worse than the channel of the intended receiver. In other words, the eavesdropper can see almost everything and yet learn almost nothing. This behavior, which contrasts sharply with that of many commonly studied wiretap channels, is made possible by the fact that a small number of linear projections can make a crucial difference in the ability to estimate sparse vectors.