We consider the problem of communicating over a channel that randomly tears the message block into small pieces of different sizes and shuffles them. For the binary torn-paper channel with block length $n$ and pieces of length ${rm Geometric}(p_n)$,
we characterize the capacity as $C = e^{-alpha}$, where $alpha = lim_{ntoinfty} p_n log n$. Our results show that the case of ${rm Geometric}(p_n)$-length fragments and the case of deterministic length-$(1/p_n)$ fragments are qualitatively different and, surprisingly, the capacity of the former is larger. Intuitively, this is due to the fact that, in the random fragments case, large fragments are sometimes observed, which boosts the capacity.
Jolfaei et al. used feedback to create transmit signals that are simultaneously useful for multiple users in a broadcast channel. Later, Georgiadis and Tassiulas studied erasure broadcast channels with feedback, and presented the capacity region unde
r certain assumptions. These results provided the fundamental ideas used in communication protocols for networks with delayed channel state information. However, to the best of our knowledge, the capacity region of erasure broadcast channels with feedback and with a common message for both receivers has never been presented. This latter problem shows up as a sub-problem in many multi-terminal communication networks such as the X-Channel, and the two-unicast problem. In this work, we present the capacity region of the two-user erasure broadcast channels with delayed feedback, private messages, and a common message. We consider arbitrary and possibly correlated erasure distributions. We develop new outer-bounds that capture feedback and quantify the impact of delivering a common message on the capacity region. We also propose a transmission strategy that achieves the outer-bounds. Our transmission strategy differs from prior results in that to achieve the capacity, it creates side-information at the weaker user such that the decodability is ensured even if we multicast the common message with a rate higher than its link capacity.
We study the impact of delayed channel state information at the transmitters (CSIT) in two-unicast wireless networks with a layered topology and arbitrary connectivity. We introduce a technique to obtain outer bounds to the degrees-of-freedom (DoF) r
egion through the new graph-theoretic notion of bottleneck nodes. Such nodes act as informational bottlenecks only under the assumption of delayed CSIT, and imply asymmetric DoF bounds of the form $mD_1 + D_2 leq m$. Combining this outer-bound technique with new achievability schemes, we characterize the sum DoF of a class of two-unicast wireless networks, which shows that, unlike in the case of instantaneous CSIT, the DoF of two-unicast networks with delayed CSIT can take an infinite set of values.
