Folded codes from function field towers and improved optimal rate list decoding
Venkatesan Guruswami, Chaoping Xing · 2012
We give a new construction of algebraic codes which are efficiently list decodable from a fraction 1-R-ε of adversarial errors where R is the rate of the code, for any desired positive constant ε. The worst-case list size output by the algorithm is O(1/ε), matching the existential bound for random codes up to constant factors. Further, the alphabet size of the codes is a constant depending only on ε --- it can be made exp(~O(1/ε2)) which is not much worse than the non-constructive exp(1/ε) bound of random codes. The 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ε(Nc) for an absolute constant $c$, where N is the code's block length. Our construction is based on a careful combination of a linear-algebraic approach to list decoding folded codes from towers of function fields, with a special form of subspace-evasive sets. Instantiating this with the explicit "asymptotically good" Garcia-Stichtenoth (GS for short) 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-size and alphabet size polylogarithmic in the block length N.