On the List-Decodability of Random Self-Orthogonal Codes

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 F_q, error fraction δ ∈ (0,1 - 1/q) satisfying 1 - H_q(δ) ≤ 1/2, and small ε > 0, with high probability a random Euclidean self-orthogonal code over F_q of rate 1 - H_q(δ) - ε 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.