论文标题
随机代码属性的阈值率
Threshold rates for properties of random codes
论文作者
论文摘要
假设$ p $是可以通过随机代码$ c \ subsetσ^n $来满足的属性。例如，对于（0,1）$中的某些$ p \，$ {p} $可能是存在$ c $的三个元素，这些元素位于某些半径$ pn $的锤子球中。我们说$ r^* $是$ {p} $的阈值率，如果一个随机的费率代码$ r^* +ε$很可能满足$ {p} $，而随机的费率代码$ r^* - ε$非常不可能满足$ {p} $。尽管随机代码在编码理论中得到了充分研究，但即使是相对简单属性的阈值率也不是对上述属性的理解。 我们表征了丰富的属性类别的阈值率。这些属性（如上示例）是由包含特定的代码字集的包含来定义的，这些代码值也适当地“对称”。对于此类的属性，我们表明阈值速率实际上等于获得的简单第一矩计算获得的下限。我们的技术不仅可以降低上面的属性$ {p} $的阈值率，而且在几个参数制度中的列表重新发现的阈值率以及估算一般列表重新发现的阈值的有效算法。
Suppose that $P$ is a property that may be satisfied by a random code $C \subset Σ^n$. For example, for some $p \in (0,1)$, ${P}$ might be the property that there exist three elements of $C$ that lie in some Hamming ball of radius $pn$. We say that $R^*$ is the threshold rate for ${P}$ if a random code of rate $R^* + ε$ is very likely to satisfy ${P}$, while a random code of rate $R^* - ε$ is very unlikely to satisfy ${P}$. While random codes are well-studied in coding theory, even the threshold rates for relatively simple properties like the one above are not well understood. We characterize threshold rates for a rich class of properties. These properties, like the example above, are defined by the inclusion of specific sets of codewords which are also suitably "symmetric". For properties in this class, we show that the threshold rate is in fact equal to the lower bound that a simple first-moment calculation obtains. Our techniques not only pin down the threshold rate for the property ${P}$ above, they give sharp bounds on the threshold rate for list-recovery in several parameter regimes, as well as an efficient algorithm for estimating the threshold rates for list-recovery in general.
