Name
Abstract | ||
|---|---|---|
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. |
Year | DOI | Venue |
|---|---|---|
2015 | 10.1109/TIT.2014.2361333 | Information Theory, IEEE Transactions |
Keywords | Field | DocType |
probability method,random codes,linear codes,list decoding,list decoding symplectic dual-containing codes,random euclidean self-orthogonal codes,self-orthogonal codes,quantum gilbert-varshamov bound,general random codes,orthogonal codes,random linear codes,decoding,fixed finite field,quantum stabilizer codes,dual codes,error fraction,vectors,polynomials | Discrete mathematics,Combinatorics,Group code,Block code,Expander code,Reed–Solomon error correction,Linear code,Reed–Muller code,Quantum convolutional code,List decoding,Mathematics | Journal |
Volume | Issue | ISSN |
abs/1611.06673 | 2 | 0018-9448 |
Citations | PageRank | References |
2 | 0.38 | 9 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Lingfei Jin | 1 | 135 | 15.30 |
| Chaoping Xing | 2 | 916 | 110.47 |
| Xiande Zhang | 3 | 52 | 15.19 |