This paper studies a variant of the Pliable Index CODing (PICOD) problem, i.e., an index coding problem where a user can be satisfied by decoding any message that is not in its side information set, where communication is decentralized, i.e., it occurs among users rather than by the central server, and secure, i.e., each user is allowed to decode only one message outside its side information set and must not be able to collect any information about any other message that is not its decoded one. Given the difficulty of the general version of this problem, this paper focuses on the case where the side information sets are `s circular shifts', namely, user u's side information set is the set of messages indexed by {u, u +1,...,u + s - 1} for some fixed s and where the indices are intended modulo the cardinality of the message set. This particular setting has been studied in the `decentralized non-secure' and in the `centralized secure' settings, thus allows one to quantify the cost of decentralized communication under security constraints on the number of transmissions. Interestingly, the decentralized vs the centralized secure setting incurs a multiplicative gap of approximately three. This is in contrast to the cases without security constraint, where the multiplicative gap is known to be at most two.

This paper studies the secure decentralized Pliable Index CODing (PICOD) problem, where the security constraint forbids users to decode more than one message while the decentralized setting imposes that there is no central transmitter in the system, and thus transmissions occur only among users. A converse bound from the Authors' previous work showed a factor of three difference in optimal code-length between the centralized and the decentralized versions of the problem, under the constraint of linear encoding. This paper first lists all linearly infeasible cases, that is, problems where no linear code can simultaneously achieve both correctness/decodability and security. Then, it proposes linear coding schemes for the remaining cases and shows that their code-length is to within an additive constant gap from the converse bound.

This paper studies the Pliable Index CODing problem (PICOD), which models content-type distribution networks. In the PICOD(t) problem there are m messages, n users and each user has a distinct message side information set, as in the classical Index Coding problem (IC). Differently from IC, where each user has a pre-specified set of messages to decode, in the PICOD(t) a user is “pliable” and is satisfied if it can decode any t messages that are not in its side information set. The goal is to find a code with the shortest length that satisfies all the users. This flexibility in determining the desired message sets makes the PICOD(t) behave quite differently compared to the IC, and its analysis even more challenging. This paper mainly focuses on the complete-S PICOD(t) with m messages, where the set S ⊂ [m] contains the sizes of the side information sets, and the number of users is n = ΣsϵS(m/s), with no two users having the same side information set. Capacity results are shown for: (i) the consecutive complete-S PICOD(t), where S = [smin: smax] for some 0 ≤ smin≤ smax≤ m-t, and (ii) the complement-consecutive complete-S PICOD(t), where S = [0 : m - t]\[smin: smax], for some 0min≤ smax<; m - t. The novel converse proof is inspired by combinatorial design techniques and the key insight is to consider all messages that a user can eventually decode successfully, even those in excess of the t required ones. This allows one to circumvent the need to consider all possible desired message set assignments at the users in order to find the one that leads to the shortest code length. The core of the novel proof is to solve the critical complete-S PICOD(t) with m = 2s + t messages and S = {s}, by showing the existence of a user who can decode s + t messages regardless of the desired message set assignment. All other tight converse results for the complete-S PICOD(t) can be deduced from this critical case. The converse results show the information theoretic optimality of simple linear coding schemes. By similar reasoning, all complete-S PICOD(t) where the number of messages is m ≤ 5 can be fully characterized. In addition, tight converse results are also shown for the PICOD(1) with circulararc network topology hypergraph.

This paper introduces the decentralized Pliable Index CODing (PICOD) problem: a variant of the Index Coding (IC) problem, where a central transmitter serves pliable users with message side information; here, pliable refers to the fact that a user is satisfied by decoding any t messages that are not in its side information set. In the decentralized PICOD, a central transmitter with knowledge of all messages is not present, and instead users share among themselves massages that can only depend on their local side information set. This paper characterizes the capacity of two classes of decentralized complete-S PICOD(t) problems with m messages (where the set S ⊂ [m] contains the sizes of the side information sets, and the number of users is n = Σs∈Sm/s, with no two users having the same side information set): (i) the consecutive case S = [smin: smax] for some 0 ≤ smin≤ smax≤ m -t, and (ii) the complement-consecutive case S = [0 : m-t]\ [smin: smax], for some 0min≤ smax≤ m - t. Interestingly, the optimal code-length for the decentralized PICOD in those cases is the same as for the classical (centralized) PICOD counterpart, except when the problem is no longer pliable, that is, it reduces to an IC problem where every user needs to decode all messages not in its side information set. Although the optimal code-length may be the same in both centralized and decentralized settings, the actual optimal codes are not. For the decentralized PICOD, sparse Maximum Distance Separable (MDS) codes and vector linear index codes are used (as opposed to scalar linear codes).

The Pliable Index CODing (PICOD) problem is a variant of the Index Coding (IC) problem, where the desired messages by the users, who are equipped with message side information, are part of the optimization. This paper studies the PICOD problem where users are subject to a privacy constraint. In particular, the following special class of private PICODs is investigated: 1) the side information structure is circular, and 2) each user can decode one and only one message. The first condition is a special case of the “circular-arc network topology hypergraph” class of PICOD studied in [6], for which an optimal solution was given without the privacy constraint. The second condition was first studied in [9] and was motivated by the need to keep content private in some distribution networks. This paper proposes both converse and achievable bounds. The proposed achievable scheme not only strictly outperforms the existing one for some values of the system parameters, but it is also information theoretically optimal in some settings. For the remaining cases, the proposed linear code is shown to require at most one more transmission than the best possible linear code.

Pliable Index CODing (PICOD) is a variant of the Index Coding (IC) problem in which a user is satisfied whenever it can successfully decode any one message that is not in its side information set, as opposed to a fixed pre-determined message. has n = Σ The complete-S PICOD with m messages, for S ⊆ [0 : m - 1], has n = Σs∈S(sm) users with distinct side information sets. Past work on PICOD provided tight converse results when either the sender is constrained to use linear codes, or for some special classes of complete-S PICOD. This paper provides a tight information theoretic converse result (i.e., no restriction to linear codes) for the so-called “consecutive complete-S” PICOD, where the set S satisfies S = [smin: smax] for some 0 ≤ smin ≤ smax ≤ m - 1. This result extends existing converse results and shows that linear codes have the smallest possible code lenght given by min (m - smin, 1 + smax). The central contribution is a novel proof technique rooted in combinatorics. The main idea is to consider all the messages a user can eventually successfully decode, in addition to its own desired message. This allows us to circumvent the necessity of essentially considering all possible assignments of desired messages for the users. The keystone of the proof is to show that, for the case of S = {s} and m = 2s + 1, there exists at least one user who can decode s + 1 messages. From this, the extension to the “consecutive complete-S” PICOD follows.

This paper provides information theoretic converse proofs for some classes of Pliable Index CODing (PICOD) problems. PICOD is a variant of the index coding problem in which a user is satisfied whenever it can successfully decode any one message that is not in its side information set. Past work on PICOD provided a number of achievable schemes based on linear codes, some of which are known to be optimal when the server is restricted to use linear codes only. This paper proves that for some of those cases linear codes are indeed optimal in an information theoretic sense, i.e., they cannot be beaten by non-linear codes. It also shows the information theoretic optimality for other classes of PICOD problems that were open.

This paper studies inner and outer bounds on the degrees of freedom (DoF) region of the multi-antenna two-user Gaussian interference channel with an instantaneous relay (IR) or relay without delay. It is assumed that the two transmitters and the two receivers have M antennas, while the IR receives through Nr antennas and transmits through Nt antennas. In the proposed achievable scheme, which generalizes a known one for the case M = Nr= Ntto any (M, Nr, Nt), the IR performs memoryless linear operations on its received signal so as to neutralize interference at the receivers, and the beamforming matrices used by the IR and the transmitters are jointly designed. This joint design strictly outperforms known achievable schemes. Two outer bounds are derived. An information theoretic outer bound is obtained by giving the receivers or the IR genie side information, so that the DoF region of the resulting enhanced channel is known; this converse is valid for any type of processing at the IR and shows the optimality of the proposed achievable scheme for some (M, Nr, Nt). A linear processing outer bound is obtained when the IR is restricted to performs linear operations, without any memoryless restriction, on its received signal and shows the optimality of the proposed achievable scheme among all linear processing schemes at the IR. As a result of independent interest, the DoF region of the classical multi-antenna two-user Gaussian interference channel without relay when the channel matrices can have any structure is also derived, which generalized available DoF region results that were derived under certain assumptions on the structure of the channel matrices.

This work studies the Pliable Index CODing problem (PICOD), a variation of the classical index coding problem where a client is satisfied if it can successfully decode at least one massage not present in its side information set. PICOD models `content-type coding' applications, such as web searches. PICOD significantly differs from classical index coding (where each client desires a specific message not present in its side information set) in the following sense. Past work showed that for PICOD O(log n) broadcast transmissions suffice to satisfy all the n clients, as opposed to the Ω(n) transmissions required by index coding; the key to this exponential improvement in number of transmissions is a probabilistic argument to show that a single transmission can satisfy at least a constant fraction of the clients. This paper elaborates further on this key result as follows. (i) A non-probabilistic analysis provides a lower bound, no smaller than 1/e, on the largest fraction of PICOD clients that can be satisfied by a single transmission in the case where all side information sets have the same cardinality; the new bound is tighter than known ones for any number of messages and clients, and sheds light into how the cardinality of the side information sets affects the number of clients satisfied by a single transmission. (ii) The same argument applied to the case where a message is in the side information set of any given client with probability p ∈ (0, 1) independent of all other messages and clients, and when there are sufficiently many messages, provides an more refined characterization of the performance than known results.

In a full-duplex bidirectional interference network with 2K transceivers, there are K communication pairs: each user transmits a message to and receives a message from one intended user and interferes with and experiences interference from all other users. All nodes may interact, or adapt inputs to past received signals, and may thus co-operate with each other. We derive a new outer bound, and use interference alignment to demonstrate that the optimal degrees of freedom (DoF, also known as the multiplexing gain) is K: full-duplex operation doubles the DoF, but interaction and co-operation does not further increase the DoF. We next characterize the DoF of a full-duplex bidirectional interference network with a MIMO full-duplex relay. If the relay is noncausal/instantaneous (at time k forwards a function of its received signals up to time k) and has 2K antennas, we demonstrate a one-shot scheme where the relay mitigates all interference to achieve the interference-free 2K DoF. In contrast, if the relay is causal (at time k forwards a function of its received signals up to time k - 1), we show that a full-duplex MIMO relay cannot increase the DoF of the full-duplex bidirectional interference network beyond K, as if no relay or interaction is present.

This paper studies the degrees of freedom (DoF) of the two-user multi-antenna Gaussian interference channel with an instantaneous relay, or relay without delay, where the relay transmitted signal in channel use t can depend on all received signals up to and including that at channel use t. It is assumed that the two transmitters and the two receivers have M antennas, while the relay receives through N antennas and transmits through L antennas. An achievable DoF is derived for all possible values of (M;N;L), based on a linear transmission strategy at the relay that aims to neutralize as much interference as possible at each destination. The proposed scheme is shown to attain the largest DoF among all linear transmission strategies at the relay and to actually be the optimal DoF for certain values of (M;N;L).