Title :
On representations of algebraic-geometry codes
Author :
Guruswami, Venkatesan ; Sudan, Madhu
Author_Institution :
Lab. for Comput. Sci., MIT, Cambridge, MA, USA
fDate :
5/1/2001 12:00:00 AM
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;
Journal_Title :
Information Theory, IEEE Transactions on
