ECCC-Report TR12-036https://eccc.weizmann.ac.il/report/2012/036Comments and Revisions published for TR12-036en-usThu, 12 Apr 2012 21:16:13 +0300
Paper TR12-036
| Folded Codes from Function Field Towers and Improved Optimal Rate List Decoding |
Venkatesan Guruswami,
Chaoping Xing
https://eccc.weizmann.ac.il/report/2012/036We 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.Thu, 12 Apr 2012 21:16:13 +0300https://eccc.weizmann.ac.il/report/2012/036