dc.contributor.authorGuruswami, Venkatesan
dc.contributor.authorXing, Chaoping
dc.date.accessioned2015-02-26T03:06:19Z
dc.date.available2015-02-26T03:06:19Z
dc.date.copyright2014en_US
dc.date.issued2014
dc.identifier.citationGuruswami, V., & Xing, C. (2014). Optimal rate list decoding of folded algebraic-geometric codes over constant-sized alphabets. Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, 1858-1866.en_US
dc.identifier.urihttp://hdl.handle.net/10220/25106
dc.description.abstractWe construct a new list-decodable family of asymptotically good algebraic-geometric (AG) codes over fixed alphabets. The function fields underlying these codes are constructed using class field theory, specifically Drinfeld modules of rank 1, and designed to have an automorphism of large order that is used to “fold” the AG code. This generalizes earlier work by the first author on folded AG codes based on cyclotomic function fields. The recent linear-algebraic approach to list decoding can be applied to our new codes, and crucially, we use the Chebotarev density theorem to establish a polynomial upper bound on the list-size for list decoding up to an error fraction approaching 1 – R where R is the rate. The list decoding can be performed in polynomial time given polynomial amount of pre-processed information about the function field.Our construction yields algebraic codes over constant-sized alphabets that can be list decoded up to the Singleton bound — specifically, for any desired rate R ∊ (0, 1) and constant ∊ > 0, we get codes over an alphabet size that can be list decoded up to error fraction 1 – R – ∊ confining close-by messages to a subspace with elements. Previous results for list decoding up to error-fraction 1 – R – ∊ over constant-sized alphabets were either based on concatenation or involved taking a carefully chosen subcode of algebraic-geometric codes. In contrast, our result shows that these folded algebraic-geometric codes themselves have the claimed list decoding property. Further, our methods to get function fields with the properties needed for constructing and decoding the code might be of independent algebraic interest.en_US
dc.format.extent9 p.en_US
dc.language.isoenen_US
dc.rights© 2014 Society for Industrial and Applied Mathematics. This paper was published in Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms and is made available as an electronic reprint (preprint) with permission of Society for Industrial and Applied Mathematics. The paper can be found at the following URL: [http://epubs.siam.org/doi/abs/10.1137/1.9781611973402.134]. One print or electronic copy may be made for personal use only. Systematic or multiple reproduction, distribution to multiple locations via electronic or other means, duplication of any material in this paper for a fee or for commercial purposes, or modification of the content of the paper is prohibited and is subject to penalties under law.en_US
dc.subjectDRNTU::Science::Mathematics::Discrete mathematics::Algorithms
dc.titleOptimal rate list decoding of folded algebraic-geometric codes over constant-sized alphabetsen_US
dc.typeConference Paper
dc.contributor.conferenceAnnual ACM-SIAM Symposium on Discrete Algorithms, SODA (25th : 2014)en_US
dc.contributor.schoolSchool of Physical and Mathematical Sciencesen_US
dc.description.versionPublished versionen_US
dc.identifier.urlhttp://epubs.siam.org/doi/abs/10.1137/1.9781611973402.134


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record