Search for: All records

Abstract We provide our perspective on$${\mathbb{X}}$$ $X$ -Learning ($${\mathbb{X}}$$ $X$ L), a novel distributed learning architecture that generalizes and extends the concept ofdecentralization. Our goal is to present a vision for$${\mathbb{X}}$$ $X$ L, introducing its unexplored design considerations and degrees of freedom. To this end, we shed light on the intuitive yet non-trivial connections between$${\mathbb{X}}$$ $X$ L, graph theory, and Markov chains. We also present a series of open research directions to stimulate further research. 

Over the last 70 years, information theory and coding has enabled communication technologies that have had an astounding impact on our lives. This is possible due to the match between encoding/decoding strategies and corresponding channel models. Traditional studies of channels have taken one of two extremes: Shannon-theoretic models are inherently average-case in which channel noise is governed by a memoryless stochastic process, whereas coding-theoretic (referred to as “Hamming”) models take a worst-case, adversarial, view of the noise. However, for several existing and emerging communication systems the Shannon/average-case view may be too optimistic, whereas the Hamming/worst-case view may be too pessimistic. This monograph takes up the challenge of studying adversarial channel models that lie between the Shannon and Hamming extremes. 

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.