Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > DETAIL:

### Paper:

TR20-169 | 11th November 2020 18:23

#### Efficient List-Decoding with Constant Alphabet and List Sizes

TR20-169
Authors: Zeyu Guo, Noga Ron-Zewi
Publication: 11th November 2020 19:07
We present an explicit and efficient algebraic construction of capacity-achieving list decodable codes with both constant alphabet and constant list sizes. More specifically, for any $R \in (0,1)$ and $\epsilon>0$, we give an algebraic construction of an infinite family of error-correcting codes of rate $R$, over an alphabet of size $(1/\epsilon)^{O(1/\epsilon^2)}$, that can be list decoded from a $(1-R-\epsilon)$-fraction of errors with list size at most $\exp(\mathrm{poly}(1/\epsilon))$. Moreover, the codes can be encoded in time $\mathrm{poly}(1/\epsilon, n)$, the output list is contained in a linear subspace of dimension at most $\mathrm{poly}(1/\epsilon)$, and a basis for this subspace can be found in time $\mathrm{poly}(1/\epsilon, n)$. Thus, both encoding and list decoding can be performed in \emph{fully polynomial-time} $\mathrm{poly}(1/\epsilon, n)$, except for pruning the subspace and outputting the final list which takes time $\exp(\mathrm{poly}(1/\epsilon)) \cdot \mathrm{poly}(n)$. In contrast, prior explicit and efficient constructions of capacity-achieving list decodable codes either required a much higher complexity in terms of $1/\epsilon$ (and were additionally much less structured), or had super-constant alphabet or list sizes.