Skip to content (access key 's')
Logo of Technion
Logo of CS Department
Logo of CS4People
Events

The Taub Faculty of Computer Science Events and Talks

On the Number of Factorizations of Polynomials with Application to List-Decoding of Rank-Metric Codes
event speaker icon
Rachel Nirit Berman (M.Sc. Thesis Seminar)
event date icon
Thursday, 04.07.2019, 14:30
event location icon
Taub 601
event speaker icon
Advisor: Prof. R.M. Roth
Rank-metric codes (RMCs) over finite fields were introduced some 40 years ago by Delsarte, Gabidulin and Roth. Interest in RMCs was revived in recent years due to the application of such codes to network coding. In 1991, another simple construction of a class of RMCs was presented by Roth, which is optimal when the field is algebraically closed. These codes are based on diagonal interleaving of maximum-distance separable (MDS) codes. In 2017, a decoding scheme was presented for these codes. In addition an upper bound on the list size was given for any list decoding radius that is smaller than the minimum rank distance. This bound is given by an expression which is independent of the field size, but crude for small fields. In this work, we address the list-decodability of the 1991 construction over finite fields, for the first nontrivial case of codes of n x n arrays with minimum distance 2 and decoding radius 1. In this case, computation of the maximum list size can be recast as an enumeration problem which may have independent mathematical interest. Specifically, given a finite field GF(q) and a positive integer n, the maximum list size equals the largest number of certain (valid) factorizations of any polynomial of degree at most 2n-2 over GF(q). In our work, we first apply combinatorial methods to obtain fairly tight upper and lower bounds on the maximum list size. We then describe the structure of polynomials that attain the maximum list size. Finally, we analyze the statistical behavior of the list size under a uniform distribution on all error arrays of rank 1. We give a closed formula for the expectation of the list size, which turns out to grow linearly with n. This implies that the list size is polynomially large in n for all but a vanishing fraction of error arrays as n goes to infinity.