{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,21]],"date-time":"2026-04-21T16:00:37Z","timestamp":1776787237640,"version":"3.51.2"},"reference-count":15,"publisher":"American Mathematical Society (AMS)","issue":"261","license":[{"start":{"date-parts":[[2008,9,13]],"date-time":"2008-09-13T00:00:00Z","timestamp":1221264000000},"content-version":"am","delay-in-days":366,"URL":"https:\/\/www.ams.org\/publications\/copyright-and-permissions"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Math. Comp."],"abstract":"

\n We define a new family of error-correcting codes based on algebraic curves over finite fields, and develop efficient list decoding algorithms for them. Our codes extend the class of algebraic-geometric (AG) codes via a (nonobvious) generalization of the approach in the recent breakthrough work of Parvaresh and Vardy (2005). Our work shows that the PV framework applies to fairly general settings by elucidating the key algebraic concepts underlying it. Also, more importantly, AG codes of arbitrary block length exist over\n fixed<\/italic>\n alphabets\n \n \n \n \n \u03a3\n \n <\/mml:mi>\n \\Sigma<\/mml:annotation>\n <\/mml:semantics>\n <\/mml:math>\n <\/inline-formula>\n , thus enabling us to establish new trade-offs between the list decoding radius and rate over a bounded alphabet size. The work of Parvaresh and Vardy (2005) was extended in Guruswami and Rudra (2006) to give explicit codes that achieve the list decoding capacity (optimal trade-off between rate and fraction of errors corrected) over large alphabets. A similar extension of this work along the lines of Guruswami and Rudra could have substantial impact. Indeed, it could give better trade-offs than currently known over a fixed alphabet (say,\n \n \n \n \n \n GF<\/mml:mtext>\n <\/mml:mrow>\n (<\/mml:mo>\n \n 2<\/mml:mn>\n \n 12<\/mml:mn>\n <\/mml:mrow>\n <\/mml:msup>\n )<\/mml:mo>\n <\/mml:mrow>\n \\textrm {GF}(2^{12})<\/mml:annotation>\n <\/mml:semantics>\n <\/mml:math>\n <\/inline-formula>\n ), which in turn, upon concatenation with a fixed, well-understood binary code, could take us closer to the list decoding capacity for binary codes. This may also be a promising way to address the significant complexity drawback of the result of Guruswami and Rudra, and to enable approaching capacity with bounded list size independent of the block length (the list size and decoding complexity in their work are both\n \n \n \n \n n<\/mml:mi>\n \n \n \u03a9\n \n <\/mml:mi>\n (<\/mml:mo>\n 1<\/mml:mn>\n \n \/<\/mml:mo>\n <\/mml:mrow>\n \n \u03b5\n \n <\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:msup>\n n^{\\Omega (1\/\\varepsilon )}<\/mml:annotation>\n <\/mml:semantics>\n <\/mml:math>\n <\/inline-formula>\n where\n \n \n \n \n \u03b5\n \n <\/mml:mi>\n \\varepsilon<\/mml:annotation>\n <\/mml:semantics>\n <\/mml:math>\n <\/inline-formula>\n is the distance to capacity). Similar to algorithms for AG codes from Guruswami and Sudan (1999) and (2001), our encoding\/decoding algorithms run in polynomial time assuming a natural polynomial-size representation of the code. For codes based on a specific \u201coptimal\u201d algebraic curve, we also present an expected polynomial time algorithm to construct the requisite representation. This in turn fills an important void in the literature by presenting an efficient construction of the representation often assumed in the list decoding algorithms for AG codes.\n <\/p>","DOI":"10.1090\/s0025-5718-07-02012-1","type":"journal-article","created":{"date-parts":[[2007,10,29]],"date-time":"2007-10-29T06:30:33Z","timestamp":1193639433000},"page":"447-473","source":"Crossref","is-referenced-by-count":8,"title":["Correlated algebraic-geometric codes: Improved list decoding over bounded alphabets"],"prefix":"10.1090","volume":"77","author":[{"given":"Venkatesan","family":"Guruswami","sequence":"first","affiliation":[]},{"given":"Anindya","family":"Patthak","sequence":"additional","affiliation":[]}],"member":"14","published-online":{"date-parts":[[2007,9,13]]},"reference":[{"issue":"1","key":"1","doi-asserted-by":"publisher","first-page":"211","DOI":"10.1007\/BF01884295","article-title":"A tower of Artin-Schreier extensions of function fields attaining the Drinfel\u2032d-Vl\u0103du\u0163 bound","volume":"121","author":"Garc\u00eda, Arnaldo","year":"1995","journal-title":"Invent. Math.","ISSN":"https:\/\/id.crossref.org\/issn\/0020-9910","issn-type":"print"},{"issue":"2","key":"2","doi-asserted-by":"publisher","first-page":"248","DOI":"10.1006\/jnth.1996.0147","article-title":"On the asymptotic behaviour of some towers of function fields over finite fields","volume":"61","author":"Garcia, Arnaldo","year":"1996","journal-title":"J. Number Theory","ISSN":"https:\/\/id.crossref.org\/issn\/0022-314X","issn-type":"print"},{"key":"3","isbn-type":"print","first-page":"658","article-title":"Expander-based constructions of efficiently decodable codes (extended abstract)","author":"Guruswami, Venkatesan","year":"2001","ISBN":"https:\/\/id.crossref.org\/isbn\/0769513905"},{"key":"4","isbn-type":"print","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/1132516.1132518","article-title":"Explicit capacity-achieving list-decodable codes or decoding up to the Singleton bound using folded Reed-Solomon codes","author":"Guruswami, Venkatesan","year":"2006","ISBN":"https:\/\/id.crossref.org\/isbn\/1595931341"},{"key":"5","isbn-type":"print","doi-asserted-by":"publisher","first-page":"159","DOI":"10.1109\/SFCS.2000.892076","article-title":"\u201cSoft-decision\u201d decoding of Chinese remainder codes","author":"Guruswami, Venkatesan","year":"2000","ISBN":"https:\/\/id.crossref.org\/isbn\/0769508502"},{"issue":"6","key":"6","doi-asserted-by":"publisher","first-page":"1757","DOI":"10.1109\/18.782097","article-title":"Improved decoding of Reed-Solomon and algebraic-geometry codes","volume":"45","author":"Guruswami, Venkatesan","year":"1999","journal-title":"IEEE Trans. Inform. Theory","ISSN":"https:\/\/id.crossref.org\/issn\/0018-9448","issn-type":"print"},{"issue":"4","key":"7","doi-asserted-by":"publisher","first-page":"1610","DOI":"10.1109\/18.923745","article-title":"On representations of algebraic-geometry codes","volume":"47","author":"Guruswami, Venkatesan","year":"2001","journal-title":"IEEE Trans. Inform. Theory","ISSN":"https:\/\/id.crossref.org\/issn\/0018-9448","issn-type":"print"},{"key":"8","unstructured":"Ralf Koetter and Alexander Vardy, Soft decoding of Reed Solomon codes and optimal weight assignments, ITG Fachtagung (Berlin, Germany), January 2002."},{"issue":"11","key":"9","doi-asserted-by":"publisher","first-page":"2809","DOI":"10.1109\/TIT.2003.819332","article-title":"Algebraic soft-decision decoding of Reed-Solomon codes","volume":"49","author":"Koetter, Ralf","year":"2003","journal-title":"IEEE Trans. Inform. Theory","ISSN":"https:\/\/id.crossref.org\/issn\/0018-9448","issn-type":"print"},{"key":"10","isbn-type":"print","volume-title":"Introduction to finite fields and their applications","author":"Lidl, Rudolf","year":"1986","ISBN":"https:\/\/id.crossref.org\/isbn\/0521307066"},{"key":"11","doi-asserted-by":"crossref","unstructured":"Farzad Parvaresh and Alexander Vardy, Correcting errors beyond the Guruswami-Sudan radius in polynomial time, Proceedings of the 46th IEEE Symposium on Foundations of Computer Science (FOCS), 2005, pp. 285\u2013294.","DOI":"10.1109\/SFCS.2005.29"},{"issue":"6","key":"12","doi-asserted-by":"publisher","first-page":"2225","DOI":"10.1109\/18.945244","article-title":"A low-complexity algorithm for the construction of algebraic-geometric codes better than the Gilbert-Varshamov bound","volume":"47","author":"Shum, Kenneth W.","year":"2001","journal-title":"IEEE Trans. Inform. Theory","ISSN":"https:\/\/id.crossref.org\/issn\/0018-9448","issn-type":"print"},{"key":"13","series-title":"Universitext","isbn-type":"print","volume-title":"Algebraic function fields and codes","author":"Stichtenoth, Henning","year":"1993","ISBN":"https:\/\/id.crossref.org\/isbn\/3540564896"},{"issue":"1","key":"14","doi-asserted-by":"publisher","first-page":"180","DOI":"10.1006\/jcom.1997.0439","article-title":"Decoding of Reed Solomon codes beyond the error-correction bound","volume":"13","author":"Sudan, Madhu","year":"1997","journal-title":"J. Complexity","ISSN":"https:\/\/id.crossref.org\/issn\/0885-064X","issn-type":"print"},{"key":"15","doi-asserted-by":"publisher","first-page":"21","DOI":"10.1002\/mana.19821090103","article-title":"Modular curves, Shimura curves, and Goppa codes, better than Varshamov-Gilbert bound","volume":"109","author":"Tsfasman, M. A.","year":"1982","journal-title":"Math. Nachr.","ISSN":"https:\/\/id.crossref.org\/issn\/0025-584X","issn-type":"print"}],"container-title":["Mathematics of Computation"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/www.ams.org\/mcom\/2008-77-261\/S0025-5718-07-02012-1\/S0025-5718-07-02012-1.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"},{"URL":"https:\/\/www.ams.org\/mcom\/2008-77-261\/S0025-5718-07-02012-1\/S0025-5718-07-02012-1.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,4,21]],"date-time":"2026-04-21T15:10:45Z","timestamp":1776784245000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.ams.org\/mcom\/2008-77-261\/S0025-5718-07-02012-1\/"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2007,9,13]]},"references-count":15,"journal-issue":{"issue":"261","published-print":{"date-parts":[[2008,1]]}},"alternative-id":["S0025-5718-07-02012-1"],"URL":"https:\/\/doi.org\/10.1090\/s0025-5718-07-02012-1","archive":["CLOCKSS","Portico"],"relation":{},"ISSN":["1088-6842","0025-5718"],"issn-type":[{"value":"1088-6842","type":"electronic"},{"value":"0025-5718","type":"print"}],"subject":[],"published":{"date-parts":[[2007,9,13]]}}}