אירועים והרצאות בפקולטה למדעי המחשב ע"ש הנרי ומרילין טאוב

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.