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

At its core, coding theory studies how many elements of a (finite) vector space one can pack subject to the constraint that the elements are well-spread. Typically, the notion of closeness is that of Hamming distance, that is, the distance between two vectors is the number of coordinates on which they differ. In a rank-metric code, codewords are matrices over a finite field and the distance between codewords is the rank of their difference. A linear rank-metric code is a subspace of matrices (over the field to which the matrix entries belong) such that every non-zero matrix in the subspace has large rank.

Rank-metric codes have found applications in magnetic recording, public-key cryptography, and space-time coding. There has been a resurgence of interest in this topic due to the utility of rank-metric codes and the closely related subspace codes for error-control in random network coding. Decoding algorithms for rank-metric codes also have connections to the popular topic of low-rank recovery, specifically in a formulation where the task is to recover a matrix H from few inner products with measurement matrices M. Finally, the study of rank-metric codes raises additional mathematical and algorithmic challenges not manifested in the Hamming metric (note that the Hamming metric case corresponds to rank-metric codes restricted to contain diagonal matrices).

In this work, the list-decodability of random linear rank-metric codes is shown to match that of uniformly random rank-metric codes. Specifically, an F_q-linear rank-metric codes over F_q^{m \times n} of rate R = (1-\rho)(1-(n/m)\rho)-\epsilon is shown to be (with high probability) list-decodable up to fractional radius \rho \in (0,1) with lists of size at most C_{\rho,q}/\epsilon, where C_{\rho,q} is a constant depending only on \rho and q. This matches the bound for uniformly random rank-metric codes, up to constant factors. The proof adapts the approach of Guruswami, Håstad, Kopparty (STOC 2010), who established a similar result for the Hamming metric case, to the rank-metric setting.

Based on joint work with Venkatesan Guruswami.