Upper Bounds on the Capacity of Binary Channels With Causal Adversaries

DOI10.1109/TIT.2013.2245721MaRDI QIDQ2989203zbMATH OpenOpenAlexWikidataFDO

Authors Bikash Kumar Dey, Sidharth Jaggi, Michael Langberg, Anand Dilip Sarwate

Publication date 8 June 2017

Published in IEEE Transactions on Information Theory (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1204.2587

Mathematics Subject Classification ID

Bounds on codes (94B65)

Abstract: In this work we consider the communication of information in the presence of a causal adversarial jammer. In the setting under study, a sender wishes to communicate a message to a receiver by transmitting a codeword $(x_1,\mathrm{...},x_n)$ bit-by-bit over a communication channel. The sender and the receiver do not share common randomness. The adversarial jammer can view the transmitted bits $x_i$ one at a time, and can change up to a $p$-fraction of them. However, the decisions of the jammer must be made in a causal manner. Namely, for each bit $x_i$ the jammer's decision on whether to corrupt it or not must depend only on $x_j$ for $jleqi$. This is in contrast to the "classical" adversarial jamming situations in which the jammer has no knowledge of $(x_1,\mathrm{...},x_n)$, or knows $(x_1,\mathrm{...},x_n)$ completely. In this work, we present upper bounds (that hold under both the average and maximal probability of error criteria) on the capacity which hold for both deterministic and stochastic encoding schemes.

Recommendations

• An Upper Bound on the Capacity of the Causal Dirty-Paper Channel
• A characterization of the capacity of online (causal) binary channels
• Bounds on the Capacity of the Relay Channel With Noncausal State at the Source
• On the Capacity of the Noncausal Relay Channel
• On Causal Source Codes With Side Information
• Capacity Bounds for Broadcast Channels With Confidential Messages
• The Capacity of Online (Causal) q -Ary Error-Erasure Channels
• Computable Upper Bounds on the Capacity of Finite-State Channels
• Upper bounds on the capacity of Gaussian channels with feedback
• scientific article; zbMATH DE number 1844484

Cited in

(2)

• The Capacity of Online (Causal) q -Ary Error-Erasure Channels
• Codes for adversaries: between worst-case and average-case jamming

This page was built for publication: Upper Bounds on the Capacity of Binary Channels With Causal Adversaries

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2989203)