2020 IEEE International Symposium
on Information Theory
21-26 June 2020 • Los Angeles, California, USA
| Paper ID | A.2.5 | ||
| Paper Title | Support Constrained Generator Matrices of Gabidulin Codes in Characteristic Zero | ||
| Authors | Hikmet Yildiz, California Institute of Technology, United States; Netanel Raviv, Washington University in Saint Louis, United States; Babak Hassibi, California Institute of Technology, United States | ||
| Session | A.2: Algebraic Coding Theory II | ||
| Presentation | Lecture | ||
| Track | Algebraic and Combinatorial Coding Theory | ||
| Manuscript | Click here to download the manuscript | ||
| Virtual Presentation | Click here to watch in the Virtual Symposium | ||
| Abstract | Gabidulin codes over fields of characteristic zero were recently constructed by Augot et al., whenever the Galois group of the underlying field extension is cyclic. In parallel, the interest in sparse generator matrices of Reed-Solomon and Gabidulin codes has increased lately, due to applications in distributed computations. In particular, a certain condition pertaining to the intersection of zero entries at different rows, was shown to be necessary and sufficient for the existence of the sparsest possible generator matrix of Gabidulin codes over finite fields. In this paper we complete the picture by showing that the same condition is also necessary and sufficient for Gabidulin codes over fields of characteristic zero. Our proof builds upon and extends tools from the finite-field case, combines them with a variant of the Schwartz-Zippel lemma over automorphisms, and provides a simple randomized construction algorithm whose probability of success can be arbitrarily close to one. In addition, potential applications for low-rank matrix recovery are discussed. | ||
Plan Ahead
2021 IEEE International Symposium on Information Theory
11-16 July 2021 | Melbourne, Victoria, Australia
