On the List-Decodability of Random Self-Orthogonal Codes
On the List-Decodability of Random Self-Orthogonal Codes
复制标题
随机自正交码的列表可译性
DOI：
10.1109/tit.2014.2361333
复制
发表时间：
2015
影响因子：
2.5
通讯作者：
Xiande Zhang
中科院分区：
文献类型：
--
作者：
Lingfei Jin;C. Xing;Xiande Zhang
Guruswami et al. showed that the list-decodability of random linear codes is as good as that of general random codes. In this paper, we further strengthen the result by showing that the list-decodability of random Euclidean self-orthogonal codes is as good as that of general random codes as well, i.e., achieves the classical Gilbert-Varshamov bound. In particular, we show that, for any fixed finite field Fq, error fraction δ ∈ (0,1 - 1/q) satisfying 1 - Hq(δ) ≤ 1/2, and small ε > 0, with high probability a random Euclidean self-orthogonal code over Fq of rate 1 - Hq(δ) - ε is (δ, O(1/ε))-list-decodable. This generalizes the result of linear codes to Euclidean self-orthogonal codes. In addition, we extend the result to list decoding symplectic dual-containing codes by showing that the list-decodability of random symplectic dual-containing codes achieves the quantum Gilbert-Varshamov bound as well. This implies that list-decodability of quantum stabilizer codes can achieve the quantum Gilbert-Varshamov bound. The counting argument on self-orthogonal codes is an important ingredient to prove our result.
Hagiya：“高阶类型理论中参数化的概括”理论计算机科学。
DOI：
--
发表时间：
--
期刊：
影响因子：
--
作者：
通讯作者：
--