Codes Against Online Adversaries: Large Alphabets
Codes Against Online Adversaries: Large Alphabets
复制标题
对抗在线对手的代码：大字母
DOI：
10.1109/tit.2013.2245717
复制
发表时间：
2013
影响因子：
2.5
通讯作者：
M. Langberg
中科院分区：
文献类型：
--
作者：
B. Dey;S. Jaggi;M. Langberg
In this paper, we consider the communication of information in the presence of an online adversarial jammer. In the setting under study, a sender wishes to communicate a message to a receiver by transmitting a codeword <b>x</b>=(<i>x</i><sub>1</sub>,...,<i>x</i><sub>n</sub>) symbol-by-symbol over a communication channel. The adversarial jammer can view the transmitted symbols <i>x</i><sub>i</sub> one at a time and can change up to a <i>p</i>-fraction of them. However, for each symbol <i>x</i><sub>i</sub>, the jammer's decision on whether to corrupt it or not (and on how to change it) must depend only on <i>x</i><sub>j</sub> for <i>j</i> ≤ <i>i</i>. This is in contrast to the “classical” adversarial jammer which may base its decisions on its complete knowledge of <b>x</b>. More generally, for a delay parameter δ ∈ (0,1), we study the scenario in which the jammer's decision on the corruption of <i>x</i><sub>i</sub> must depend solely on <i>x</i><sub>j</sub> for <i>j</i> ≤ <i>i</i>-δ<i>n</i>. In this study, the transmitted symbols are assumed to be over a sufficiently large field F. The sender and receiver do not share resources such as common randomness (though the sender is allowed to use stochastic encoding). We present a tight characterization of the amount of information one can transmit in both the 0-delay and, more generally, the δ-delay online setting. We show that for 0-delay adversaries, the achievable rate asymptotically equals that of the classical adversarial model. For positive values of δ, we consider two types of jamming: additive and overwrite. We also extend our results to a jam-or-listen online model, where the online adversary can either jam a symbol or eavesdrop on it. We present computationally efficient achievability schemes even against computationally unrestricted jammers.
