Vol. 4, No. 4, 2010

Download this article
Download this article For screen
For printing
Recent Issues

Volume 18
Issue 5, 847–1038
Issue 4, 631–846
Issue 3, 409–629
Issue 2, 209–408
Issue 1, 1–208

Volume 17, 12 issues

Volume 16, 10 issues

Volume 15, 10 issues

Volume 14, 10 issues

Volume 13, 10 issues

Volume 12, 10 issues

Volume 11, 10 issues

Volume 10, 10 issues

Volume 9, 10 issues

Volume 8, 10 issues

Volume 7, 10 issues

Volume 6, 8 issues

Volume 5, 8 issues

Volume 4, 8 issues

Volume 3, 8 issues

Volume 2, 8 issues

Volume 1, 4 issues

The Journal
About the Journal
Editorial Board
Editors’ Interests
Submission Guidelines
Submission Form
Policies for Authors
Ethics Statement
ISSN: 1944-7833 (e-only)
ISSN: 1937-0652 (print)
Author Index
To Appear
Other MSP Journals
Cyclotomic function fields, Artin–Frobenius automorphisms, and list error correction with optimal rate

Venkatesan Guruswami

Vol. 4 (2010), No. 4, 433–463

Algebraic error-correcting codes that achieve the optimal trade-off between rate and fraction of errors corrected (in the model of list decoding) were recently constructed by a careful “folding” of the Reed–Solomon code. The “low-degree” nature of this folding operation was crucial to the list decoding algorithm. We show how such folding schemes useful for list decoding arise out of the Artin–Frobenius automorphism at primes in Galois extensions. Using this approach, we construct new folded algebraic-geometric codes for list decoding based on cyclotomic function fields with a cyclic Galois group. Such function fields are obtained by adjoining torsion points of the Carlitz action of an irreducible M Fq[T]. The Reed–Solomon case corresponds to the simplest such extension (corresponding to the case M = T). In the general case, we need to descend to the fixed field of a suitable Galois subgroup in order to ensure the existence of many degree 1 places that can be used for encoding.

Our methods shed new light on algebraic codes and their list decoding, and lead to new codes with optimal trade-off between rate and error correction radius. Quantitatively, these codes provide list decoding (and list recovery/soft decoding) guarantees similar to folded Reed–Solomon codes but with an alphabet size that is only polylogarithmic in the block length. In comparison, for folded RS codes, the alphabet size is a large polynomial in the block length. This has applications to fully explicit (with no brute-force search) binary concatenated codes for list decoding up to the Zyablov radius.

list decoding, algebraic-geometric codes, Galois extensions, Cyclotomic function fields, Reed–Solomon codes, Frobenius automorphisms
Mathematical Subject Classification 2000
Primary: 11R60
Secondary: 14Q05, 11G30, 94B27, 12Y05, 68Q30
Received: 29 June 2009
Revised: 5 January 2010
Accepted: 17 February 2010
Published: 13 June 2010
Venkatesan Guruswami
Computer Science Department
Carnegie Mellon University
Pittsburgh, PA 15213
United States