Search for: All records

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. 

This work addresses the cooperation facilitator (CF) model, in which network nodes coordinate through a rate limited communication device. For multiple-access channel (MAC) encoders, the CF model is known to show significant rate benefits, even when the rate of cooperation is negligible. Specifically, the benefit in MAC sum-rate, as a function of the cooperation rate C_{CF}, sometimes has an infinite slope at C_{CF} = 0 when the CF enables transmitter dependence where none was possible otherwise. This work asks whether cooperation through a CF can yield similar infinite-slope benefits when dependence among MAC transmitters has no benefit or when it can be established without the help of the CF. Specifically, this work studies the CF model when applied to relay nodes of a single-source, single-terminal, diamond network comprising a broadcast channel followed by a MAC. In the relay channel with orthogonal receiver components, careful generalization of the partial-decode-forward/compress-forward lower bound to the CF model yields sufficient conditions for an infinite-slope benefit. Additional results include derivation of a family of diamond networks for which the infinite-slope rate-benefit derives directly from the properties of the corresponding MAC studied in isolation. 

The work at hand presents a finite-blocklength analysis of the multiple access channel (MAC) sum-rate under the cooperation facilitator (CF) model. The CF model, in which independent encoders coordinate through an intermediary node, is known to show significant rate benefits, even when the rate of cooperation is limited. We continue this line of study for cooperation rates which are sub-linear in the blocklength n. Roughly speaking, our results show that if the facilitator transmits log K bits, then there is a sum-rate benefit of order √log K/n compared to the best-known achievable rate. This result extends across a wide range of K: even a single bit of cooperation is shown to provide a sum-rate benefit of order 1/√n.