On representations of algebraic-geometry codes
We show that all algebraic-geometric codes possess a succinct representation that allows for the list decoding algorithms of [9], [6] 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.
succinct representations list decoding algebraic function fields root finding