Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR12-036 | 12th April 2012 21:15

Folded Codes from Function Field Towers and Improved Optimal Rate List Decoding



We give a new construction of algebraic codes which are efficiently list decodable from a fraction $1-R-\epsilon$ of adversarial errors where $R$ is the rate of the code, for any desired positive constant $\epsilon$. The worst-case list size output by the algorithm is $O(1/\epsilon)$, matching the existential bound for random codes up to constant factors. Further, the alphabet size of the codes is a constant depending only on $\epsilon$ --- it can be made $\exp(\tilde{O}(1/\epsilon^2))$ which is not much worse than the lower bound of $\exp(\Omega(1/\epsilon))$. The parameters we achieve are thus quite close to the existential bounds in all three aspects --- error-correction radius, alphabet size, and list-size --- simultaneously. Our code construction is Monte Carlo and has the claimed list decoding property with high probability. Once the code is (efficiently) sampled, the encoding/decoding algorithms are deterministic with a running time $O_{\epsilon}(N^c)$ for an absolute constant $c$, where $N$ is the code's block length.

Our construction is based on a linear-algebraic approach to list decoding folded codes from towers of function fields, and combining it with a special form of subspace-evasive sets. Instantiating this with the explicit ``asymptotically good" Garcia-Stichtenoth tower of function fields yields the above parameters. To illustrate the method in a simpler setting, we also present a construction based on Hermitian function fields, which offers similar guarantees with a list and alphabet size polylogarithmic in the block length $N$. Along the way, we shed light on how to use automorphisms of certain function fields to enable list decoding of the folded version of the associated algebraic-geometric codes.

ISSN 1433-8092 | Imprint