论文标题
在限制下，遗忘的AVC的紧密列表尺寸
Tight List-Sizes for Oblivious AVCs under Constraints
论文作者
论文摘要
我们研究了由遗忘对手（又称任意变化的渠道（AVC））控制的对抗渠道的列表。这种对手的目的是在不知道发件人的实际传输的情况下恶意破坏沟通。对于任何可能对发件人传输序列和对手噪声序列的约束的遗忘AVC，我们确定可以以正速率支持可靠通信的最小列表大小的确切值。这概括了休斯（IEEE信息理论，1997年的IEEE交易）的经典结果，并回答了Sarwate和Gastpar提出的一个公开问题（IEEE信息理论交易，2012年）。列出列表解码能力（每当阳性）的下限。在某个组合猜想下，我们还证明了匹配的上限。在对列表描述能力的紧密表征的途径中，我们提出了一种子代码构造的方法，以解决组合构想的分辨率。
We study list-decoding over adversarial channels governed by oblivious adversaries (a.k.a. oblivious Arbitrarily Varying Channels (AVCs)). This type of adversaries aims to maliciously corrupt the communication without knowing the actual transmission from the sender. For any oblivious AVCs potentially with constraints on the sender's transmitted sequence and the adversary's noise sequence, we determine the exact value of the minimum list-size that can support a reliable communication at positive rate. This generalizes a classical result by Hughes (IEEE Transactions on Information Theory, 1997) and answers an open question posed by Sarwate and Gastpar (IEEE Transactions on Information Theory, 2012). A lower bound on the list-decoding capacity (whenever positive) is presented. Under a certain combinatorial conjecture, we also prove a matching upper bound. En route to a tight characterization of the list-decoding capacity, we propose a method for subcode construction towards the resolution of the combinatorial conjecture.
