Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > DETAIL:

### Paper:

TR15-161 | 24th September 2015 14:06

#### A new class of rank-metric codes and their list decoding beyond the unique decoding radius

TR15-161
Authors: Chaoping Xing, chen yuan
Publication: 30th September 2015 16:43
Keywords:

Abstract:

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 $\rho(\mC)$ is extremely small, i.e., $\Theta(\Ge^2)$ , where $\rho(\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 $\rho(\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 $\rho(\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 ${\Ge}>0$ be a small real. Let $q=r^{\ell}$ with $\gcd(r-1,\ell n)=1$. Then there exists an explicit rank-metric code $\mC$ in $\MM_{n\times(r-1)n}(\F_q)$ with rate ${R}$ that is $({\tau}, O(\exp(1/{\Ge^2})))$-list decodable with ${\tau}=\frac c{c+1}\left(1-\frac{r-1}{r-c}\times {R}-{\Ge}\right)$. Furthermore, encoding and list-decoding algorithms are in polynomial time ${\rm poly}(n,\exp(1/{\Ge}))$. The list size can be reduced to $O(1/{\Ge})$ by randomizing the algorithm. Note that the ratio $\rho(\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.

ISSN 1433-8092 | Imprint