DocumentCode
1490791
Title
On representations of algebraic-geometry codes
Author
Guruswami, Venkatesan ; Sudan, Madhu
Author_Institution
Lab. for Comput. Sci., MIT, Cambridge, MA, USA
Volume
47
Issue
4
fYear
2001
fDate
5/1/2001 12:00:00 AM
Firstpage
1610
Lastpage
1613
Abstract
We show that all algebraic-geometric codes possess a succinct representation that allows for list decoding algorithms to run in polynomial time. We do this by presenting a root-finding algorithm for univariate polynomials over function fields when their coefficients lie in finite-dimensional linear spaces, and proving that there is a polynomial size representation, given which the root-finding algorithm runs in polynomial time
Keywords
algebraic geometric codes; decoding; error correction codes; polynomials; algebraic-geometry codes; finite-dimensional linear spaces; list decoding algorithms; polynomial size representation; polynomial time; root-finding algorithm; succinct representation; univariate polynomials; Arithmetic; Computer science; Decoding; Engineering profession; Error correction codes; Polynomials;
fLanguage
English
Journal_Title
Information Theory, IEEE Transactions on
Publisher
ieee
ISSN
0018-9448
Type
jour
DOI
10.1109/18.923745
Filename
923745
Link To Document