On the capacity of memoryless adversary
On the capacity of memoryless adversary
复制标题
论无记忆对手的能力
DOI：
10.1109/isit.2014.6875358
复制
发表时间：
2014
期刊：
影响因子：
--
通讯作者：
A. Mazumdar
中科院分区：
文献类型：
--
作者：
A. Mazumdar
本文研究了对抗性噪声下的通信模型。在此模型中，攻击者仅根据传输比特的值在线决定是否损坏该比特。就像通常的信息理论的二进制对称信道或组合编码理论的完全对抗性信道一样，敌手可能以很高的概率引入至多一个给定的错误分数。结果表明，这种无记忆敌手的容量(可靠信息传输的最大速率)严格低于二进制对称信道的容量。我们对这种通道的容量给出了新的上限--这个上限的紧密性仍然是一个悬而未决的问题。我们证明的主要部分是仔细研究具有倾斜距离分布的码的纠错性质。
In this paper, we study a model of communication under adversarial noise. In this model, the adversary makes online decisions on whether to corrupt a transmitted bit based on only the value of that bit. Like the usual binary symmetric channel of information theory or the fully adversarial channel of combinatorial coding theory, the adversary can, with high probability, introduce at most a given fraction of error. It is shown that, the capacity (maximum rate of reliable information transfer) of such memoryless adversary is strictly below that of the binary symmetric channel. We give new upper bound on the capacity of such channel - the tightness of this upper bound remains an open question. The main component of our proof is the careful examination of error-correcting properties of a code with skewed distance distribution.
影响因子：
2.5
作者：
Guruswami, Venkatesan;Smith, Adam
通讯作者：
Smith, Adam