2020/04/29 by Hikmet Yıldız, Yildiz, Hikmet, Netanel Raviv +3
Computer Science · #Coding theory and cryptography #Cooperative Communication and Network Coding #Error Correcting Code Techniques #FOS: Computer and information sciences #Information Theory (cs.IT)
paper · pdf · doi:10.48550/arxiv.2004.14430
openalex publication_date 2020/04/29 · openalex created_date 2022/07/18 · openalex updated_date 2026/07/28
Gabidulin codes over fields of characteristic zero were recently constructed\nby Augot et al., whenever the Galois group of the underlying field extension is\ncyclic. In parallel, the interest in sparse generator matrices of Reed-Solomon\nand Gabidulin codes has increased lately, due to applications in distributed\ncomputations. In particular, a certain condition pertaining the intersection of\nzero entries at different rows, was shown to be necessary and sufficient for\nthe existence of the sparsest possible generator matrix of Gabidulin codes over\nfinite fields. In this paper we complete the picture by showing that the same\ncondition is also necessary and sufficient for Gabidulin codes over fields of\ncharacteristic zero. Our proof builds upon and extends tools from the finite\nfield case, combines them with a variant of the Schwartz-Zippel lemma over\nautomorphisms, and provides a simple randomized construction algorithm whose\nprobability of success can be arbitrarily close to one. In addition, potential\napplications for low-rank matrix recovery are discussed.\n