2026-07-23T21:03:19Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:24409 2025-12-12T15:01:34Z ddc:004 open_access

Gabidulin Codes Achieve List Decoding Capacity with an Order-Optimal Column-To-Row Ratio Guo, Zeyu Xing, Chaoping Yuan, Chen Zhang, Zihan coding theory error-correcting codes Gabidulin codes rank-metric codes In this paper, we show that random Gabidulin codes of block length n and rate R achieve the (average-radius) list decoding capacity of radius 1-R-ε in the rank metric with an order-optimal column-to-row ratio of O(ε). This extends the recent work of Guo, Xing, Yuan, and Zhang (FOCS 2024), improving their column-to-row ratio from O(ε/n) to O(ε). For completeness, we also establish a matching lower bound on the column-to-row ratio for capacity-achieving Gabidulin codes in the rank metric. Our proof techniques build on the work of Guo and Zhang (FOCS 2023), who showed that randomly punctured Reed-Solomon codes over fields of quadratic size attain the generalized Singleton bound of Shangguan and Tamo (STOC 2020) in the Hamming metric. The proof of our lower bound follows the method of Alrabiah, Guruswami, and Li (SODA 2024) for codes in the Hamming metric. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Zeyu Guo and Chaoping Xing and Chen Yuan and Zihan Zhang 2025 Is Part Of LIPIcs, Volume 353, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2025) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.APPROX/RANDOM.2025.43 urn:nbn:de:0030-drops-244095 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2025.43 eng https://creativecommons.org/licenses/by/4.0/legalcode