On the list decodability of random linear codes with large error rates
On the list decodability of random linear codes with large error rates
复制标题
大误码率随机线性码的可译性列表
DOI：
--
复制
发表时间：
2013
期刊：
影响因子：
--
通讯作者：
Mary Wootters
中科院分区：
文献类型：
--
作者：
Mary Wootters
众所周知，随机Q -ARY速率代码ω（ε2）的列表可解码至半径（1-1/q -ε），列表大小为1/ε2，概率为1 -o（1）但是，直到最近，关于随机线性代码的类似说明，直到最近的论文中，cheraghchi，guruswami和velingker都显示传感，并使用此连接证明速率ω（ε2/log3（1/ε））的随机线性代码可实现上面的列表解码属性，而我们可以提高其结果。率为最佳的ω（ε2），而成功的概率为1 -o（1），而不是恒定的好处，我们的证明是相对简单的。一般的合奏线性代码。
It is well known that a random q-ary code of rate Ω(ε2) is list decodable up to radius (1 - 1/q - ε) with list sizes on the order of 1/ε2, with probability 1 - o(1). However, until recently, a similar statement about random linear codes has until remained elusive. In a recent paper, Cheraghchi, Guruswami, and Velingker show a connection between list decodability of random linear codes and the Restricted Isometry Property from compressed sensing, and use this connection to prove that a random linear code of rate Ω( ε2 /log3(1/ε)) achieves the list decoding properties above, with constant probability. We improve on their result to show that in fact we may take the rate to be Ω(ε2), which is optimal, and further that the success probability is 1 - o(1), rather than constant. As an added benefit, our proof is relatively simple. Finally, we extend our methods to more general ensembles of linear codes. As an example, we show that randomly punctured Reed-Muller codes have the same list decoding properties as the original codes, even when the rate is improved to a constant.