Compared with classical block codes, efficient list decoding of rank-metric codes seems more difficult. The evidences to support this view include: (i) so far people have not found polynomial time list decoding algorithms of rank-metric codes with decoding radius beyond (1 − R ) 2 (where R is the rate of code) if ratio of the number of rows over the number of columns is constant, but not very small; (ii) the Johnson bound for rank-metric codes does not exist as opposed to classical codes; (iii) the Gabidulin codes can not be list decoded beyond half of minimum distance. Although the list decodability of random rank-metric codes and limits to list decodability have been completely determined, little work on efficient list decoding rank-metric codes has been done. The only known efficient list decoding of rank-metric codes \mC gives decoding radius up to the Singleton bound 1 − R − \Ge with positive rate R when ( \mC ) is extremely small, i.e., ( \Ge 2 ) , where ( \mC ) denotes the ratio of the number of rows over the number of columns of \mC \cite[STOC2013]{Guru2013}. It is commonly believed that list decoding of rank-metric codes \mC with not small constant ratio ( \mC ) is hard.

The main purpose of the present paper is to explicitly construct a class of rank-metric codes \mC with not small constant ratio ( \mC ) and efficiently list decode these codes with decoding radius beyond (1 − R ) 2 . Specifically speaking, let r be a prime power and let c be an integer between 1 and r − 1 . Let 0"> \Ge 0 be a small real. Let q = r with gcd ( r − 1 n ) = 1 . Then there exists an explicit rank-metric code \mC in \MM n ( r − 1) n ( \F q ) with rate R that is ( O ( exp (1 \Ge 2 ))) -list decodable with = c c +1 1 − r − 1 r − c R − \Ge . Furthermore, encoding and list-decoding algorithms are in polynomial time pol y ( n exp (1 \Ge )) . The list size can be reduced to O (1 \Ge ) by randomizing the algorithm. Note that the ratio ( \mC ) for our code \mC is 1 ( r − 1 ) . Our key idea is to employ two-variable polynomials f ( x y ) , where f is linearized in variable x and the variable y is used to ``fold" the code. In other words, rows are used to correct rank errors and columns are used to ``fold" the code to enlarge decoding radius. Apart from the above algebraic technique, we have to prune down the list. The algebraic idea enables us to pin down the messages into a structured subspace of dimension linear in the number n of columns. This ``periodic" structure allows us to pre-encoding the messages to prune down the list. More precisely, we use subspace design introduced in \cite[STOC2013]{Guru2013} to get a deterministic algorithm with a larger constant list size and employ hierarchical subspace-evasive sets introduced in \cite[STOC2012]{Guru2012} to obtain a randomized algorithm with a smaller constant list size.