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 :
بازگشت