{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,28]],"date-time":"2026-02-28T12:58:52Z","timestamp":1772283532055,"version":"3.50.1"},"publisher-location":"Berlin, Heidelberg","reference-count":39,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783540429111","type":"print"},{"value":"9783540456247","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2001]]},"DOI":"10.1007\/3-540-45624-4_4","type":"book-chapter","created":{"date-parts":[[2007,6,2]],"date-time":"2007-06-02T23:23:35Z","timestamp":1180826615000},"page":"36-45","source":"Crossref","is-referenced-by-count":11,"title":["Ideal Error-Correcting Codes: Unifying Algebraic and Number-Theoretic Algorithms"],"prefix":"10.1007","author":[{"given":"Madhu","family":"Sudan","sequence":"first","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2001,10,31]]},"reference":[{"issue":"2","key":"4_CR1","doi-asserted-by":"publisher","first-page":"487","DOI":"10.1137\/S0097539796297577","volume":"28","author":"S. Ar","year":"1999","unstructured":"Sigal Ar, Richard J. Lipton, Ronitt Rubinfeld, and Madhu Sudan. Reconstructing algebraic functions from erroneous data. SIAM Journal on Computing, 28(2): 487\u2013510, April 1999.","journal-title":"SIAM Journal on Computing"},{"issue":"6","key":"4_CR2","first-page":"2605","volume":"46","author":"D. Augot","year":"2000","unstructured":"Daniel Augot and Lancelot Pecquet. A Hensel lifting to replace factorization inlist decoding of algebraic-geometric and Reed-Solomon codes. IEEE Trans. Info.Theory, 46(6): 2605\u20132613, November 2000.","journal-title":"IEEE Trans. Info.Theory"},{"issue":"3","key":"4_CR3","doi-asserted-by":"publisher","first-page":"704","DOI":"10.1109\/18.490539","volume":"42","author":"E.R. Berlekamp","year":"1996","unstructured":"Elwyn R.Berlekamp. Bounded distance +1 soft-decision Reed Solomon decoding.IEEE Transactions on Information Theory, 42(3):704\u2013720, 1996.","journal-title":"IEEE Transactions on Information Theory"},{"key":"4_CR4","unstructured":"Richard E. Blahut. Theory and practice of error control codes. Addison-Wesley Pub. Co., 1983."},{"issue":"1","key":"4_CR5","first-page":"11","volume":"22","author":"V. M. Blinovskii","year":"1986","unstructured":"V. M. Blinovskii. Bounds for codes in the case of list decoding of finite volume.Problemy Peradachi Informatsii, 22(1):11\u201325, January-March 1986.","journal-title":"Problemy Peradachi Informatsii"},{"key":"4_CR6","doi-asserted-by":"crossref","unstructured":"Dan Boneh. Finding smooth integers in short intervals using CRT decoding. (Toappear) Proceedings of the Thirty-Second Annual ACM Symposium on Theory ofComputing, Portland, Oregon, 21\u201323 May 2000.","DOI":"10.1145\/335305.335337"},{"key":"4_CR7","unstructured":"Peter Elias. List decoding for noisy channels. WESCON Convention Record, Part2, Institute of Radio Engineers (now IEEE), pages 94\u2013104, 1957."},{"issue":"1","key":"4_CR8","doi-asserted-by":"publisher","first-page":"5","DOI":"10.1109\/18.61123","volume":"37","author":"P. Elias","year":"1991","unstructured":"Peter Elias. Error-correcting codes for list decoding. IEEE Transactions on InformationTheory, 37(1):5\u201312, January 1991.","journal-title":"IEEE Transactions on InformationTheory"},{"issue":"1","key":"4_CR9","doi-asserted-by":"publisher","first-page":"37","DOI":"10.1109\/18.179340","volume":"39","author":"G.-L. Feng","year":"1993","unstructured":"G.-L. Feng and T. R. N. Rao. Decoding algebraic-geometric codes upto the designedminimum distance. IEEE Transactions on Information Theory, 39(1):37\u201345,January 1993.","journal-title":"IEEE Transactions on Information Theory"},{"key":"4_CR10","volume-title":"Concatenated Codes","author":"G. D. Forney Jr.","year":"1966","unstructured":"G. David Forney Jr.. Concatenated Codes. MIT Press, Cambridge, MA, 1966."},{"key":"4_CR11","doi-asserted-by":"crossref","unstructured":"S. Gao and M. A. Shokrollahi. Computing roots of polynomials over function fields of curves. Proceedings of the Annapolis Conference on Number Theory, CodingTheory, and Cryptography, 1999.","DOI":"10.1007\/978-3-642-59663-6_12"},{"issue":"4","key":"4_CR12","doi-asserted-by":"publisher","first-page":"1330","DOI":"10.1109\/18.850672","volume":"46","author":"O. Goldreich","year":"2000","unstructured":"Oded Goldreich, Dana Ron, and Madhu Sudan. Chinese remaindering with errors.IEEE Transactions on Information Theory. 46(4): 1330\u20131338, July 2000.","journal-title":"IEEE Transactions on Information Theory"},{"key":"4_CR13","doi-asserted-by":"crossref","unstructured":"Oded Goldreich, Ronitt Rubinfeld, and Madhu Sudan. Learning polynomials withqueries: The highly noisy case. Proceedings of the 36th Annual Symposium onFoundations of Computer Science, pages 294\u2013303, Milwaukee, Wisconsin, 23\u201325 October 1995.","DOI":"10.1109\/SFCS.1995.492485"},{"key":"4_CR14","first-page":"20","volume":"137","author":"D. Grigoriev","year":"1984","unstructured":"Dima Grigoriev. Factorization of polynomials over a finite field and the solutionof systems of algebraic equations. Translated from Zapiski Nauchnykh SeminarovLenningradskogo Otdeleniya Matematicheskogo Instituta im. V. A. Steklova ANSSSR, 137:20\u201379, 1984.","journal-title":"Zapiski Nauchnykh SeminarovLenningradskogo Otdeleniya Matematicheskogo Instituta im. V. A. Steklova ANSSSR"},{"key":"4_CR15","unstructured":"Venkatesan Guruswami, Johan H\u00e5stad, Madhu Sudan, and David Zuckerman.Combinatorial bounds for list decoding. (To appear) Proceedings of the 38th AnnualAllerton Conference on Communication, Control, and Computing, 2000."},{"key":"4_CR16","doi-asserted-by":"crossref","unstructured":"Venkatesan Guruswami, Amit Sahai, and Madhu Sudan. \u201cSoft-decision\u201d decodingof Chinese remainder codes. Proceedings of the 41st Annual Symposium on Foundationsof Computer Science, pages 159\u2013168, Redondo Beach, California, 12\u201314November, 2000.","DOI":"10.1109\/SFCS.2000.892076"},{"issue":"6","key":"4_CR17","doi-asserted-by":"publisher","first-page":"1757","DOI":"10.1109\/18.782097","volume":"45","author":"V. Guruswami","year":"1999","unstructured":"Venkatesan Guruswami and Madhu Sudan. Improved decoding of Reed-Solomoncodes and algebraic-geometric codes. IEEE Transactions on Information Theory,45(6): 1757\u20131767, September 1999.","journal-title":"IEEE Transactions on Information Theory"},{"key":"4_CR18","doi-asserted-by":"crossref","unstructured":"Venkatesan Guruswami and Madhu Sudan. List decoding algorithms for certainconcatenated codes. Proceedings of the Thirty-Second Annual ACM Symposiumon Theory of Computing, pages 181\u2013190, Portland, Oregon, 21\u201323 May 2000.","DOI":"10.1145\/335305.335327"},{"key":"4_CR19","unstructured":"Venkatesan Guruswami and Madhu Sudan, On representations of algebraicgeometriccodes. IEEE Transactions on Information Theory (to appear)."},{"key":"4_CR20","unstructured":"T. H\u00f8holdt, J. H. van Lint, and R. Pellikaan. Algebraic geometry codes. In Handbookof Coding Theory, V. Pless and C. Huffman (Eds.), Elsevier Sciences, 1998."},{"key":"4_CR21","unstructured":"J. Justesen and T. H\u00f8holdt. Bounds on list decoding of MDS codes. Manuscript,1999."},{"key":"4_CR22","doi-asserted-by":"crossref","unstructured":"Erich Kaltofen. A polynomial-time reduction from bivariate to univariate integralpolynomial factorization. Proceedings of the Fourteenth Annual ACM Symposiumon Theory of Computing, pages 261\u2013266, San Francisco, California, 5\u20137 May 1982.","DOI":"10.1145\/800070.802200"},{"key":"4_CR23","unstructured":"Ralf K\u00f6tter and Alexander Vardy. Algebraic soft-decision decoding of Reed-Solomon codes. (To appear) Proceedings of the 38th Annual Allerton Conferenceon Communication, Control, and Computing, 2000."},{"issue":"2","key":"4_CR24","doi-asserted-by":"publisher","first-page":"235","DOI":"10.1016\/0022-0000(85)90016-9","volume":"30","author":"A.K. Lenstra","year":"1985","unstructured":"Arjen K. Lenstra. Factoring multivariate polynomials over finite fields. Journal ofComputer and System Sciences, 30(2):235\u2013248, April 1985.","journal-title":"Journal ofComputer and System Sciences"},{"key":"4_CR25","doi-asserted-by":"publisher","first-page":"515","DOI":"10.1007\/BF01457454","volume":"261","author":"A. K. Lenstra","year":"1982","unstructured":"A. K. Lenstra, H. W. Lenstra, and L. Lovasz. Factoring polynomials with rationalcoefficients. Mathematische Annalen, 261:515\u2013534, 1982.","journal-title":"Mathematische Annalen"},{"key":"4_CR26","doi-asserted-by":"publisher","first-page":"85","DOI":"10.1109\/TIT.1976.1055504","volume":"21","author":"D. M. Mandelbaum","year":"1976","unstructured":"D. M. Mandelbaum. On a class of arithmetic codes and a decoding algorithm.IEEE Transactions on Information Theory, 21:85\u201388, 1976.","journal-title":"IEEE Transactions on Information Theory"},{"key":"4_CR27","unstructured":"R. Matsumoto. On the second step in the Guruswami-Sudan list decoding algorithmfor AG-codes. Technical Report of IEICE, pp. 65\u201370, 1999."},{"key":"4_CR28","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"260","DOI":"10.1007\/3-540-48236-9","volume-title":"Proceedings of AAECC-13","author":"R. R. Nielsen","year":"1999","unstructured":"R. Refslund Nielsen and Tom H\u00f8holdt. Decoding Hermitian codes with Sudan\u2019salgorithm. Proceedings of AAECC-13, LNCS 1719, Springer-Verlag, 1999, pp. 260\u2013270."},{"key":"4_CR29","doi-asserted-by":"publisher","first-page":"459","DOI":"10.1109\/TIT.1960.1057586","volume":"IT-60","author":"W. W. Peterson","year":"1960","unstructured":"W. W. Peterson. Encoding and error-correction procedures for Bose-Chaudhuricodes. IRE Transactions on Information Theory, IT-60:459\u2013470, 1960.","journal-title":"IRE Transactions on Information Theory"},{"issue":"1","key":"4_CR30","doi-asserted-by":"publisher","first-page":"246","DOI":"10.1109\/18.817522","volume":"46","author":"R. M. Roth","year":"2000","unstructured":"Ron M. Roth and Gitit Ruckenstein. Efficient decoding of Reed-Solomon codesbeyond half the minimum distance. IEEE Transactions on Information Theory,46(1):246\u2013257, January 2000.","journal-title":"IEEE Transactions on Information Theory"},{"key":"4_CR31","doi-asserted-by":"crossref","unstructured":"Madhu Sudan, Luca Trevisan, and Salil Vadhan. Pseudorandom generation withoutthe XOR lemma. Proceedings of the Thirty-First Annual ACM Symposiumon Theory of Computing, pages 537\u2013546, Atlanta, Georgia, 1\u20134 May 1999.","DOI":"10.1145\/301250.301397"},{"issue":"2","key":"4_CR32","doi-asserted-by":"publisher","first-page":"432","DOI":"10.1109\/18.748993","volume":"45","author":"M. A. Shokrollahi","year":"1999","unstructured":"M. Amin Shokrollahi and Hal Wasserman. List decoding of algebraic-geometriccodes. IEEE Transactions on Information Theory, 45(2): 432\u2013437, March 1999.","journal-title":"IEEE Transactions on Information Theory"},{"key":"4_CR33","volume-title":"Algebraic Function Fields and Codes","author":"H. Stichtenoth","year":"1993","unstructured":"Henning Stichtenoth. Algebraic Function Fields and Codes. Springer-Verlag, Berlin,1993."},{"key":"4_CR34","series-title":"Lect Notes Comput Sci","volume-title":"Efficient Checking of Polynomials and Proofs and the Hardness ofApproximations","author":"M. Sudan","year":"1996","unstructured":"Madhu Sudan. Efficient Checking of Polynomials and Proofs and the Hardness ofApproximations. ACM Distinguished Theses. Lecture Notes in Computer Science,no. 1001, Springer, 1996."},{"issue":"1","key":"4_CR35","doi-asserted-by":"publisher","first-page":"180","DOI":"10.1006\/jcom.1997.0439","volume":"13","author":"M. Sudan","year":"1997","unstructured":"Madhu Sudan. Decoding of Reed Solomon codes beyond the error-correctionbound. Journal of Complexity, 13(1): 180\u2013193, March 1997.","journal-title":"Journal of Complexity"},{"key":"4_CR36","unstructured":"Lloyd Welch and Elwyn R. Berlekamp. Error correction of algebraic block codes. US Patent Number 4,633,470, issued December 1986."},{"key":"4_CR37","first-page":"90","volume":"48","author":"J. M. Wozencraft","year":"1958","unstructured":"J. M. Wozencraft. List decoding. Quarterly Progress Report. Research Laboratory of Electronics, MIT, Vol. 48, pp. 90\u201395, 1958.","journal-title":"List decoding"},{"key":"4_CR38","unstructured":"Xin-Wen Wu and Paul H. Siegel. Efficient list decoding of algebraic geometriccodes beyond the error correction bound. Proc. of International Symposium onInformation Theory, June 2000."},{"issue":"4","key":"4_CR39","first-page":"29","volume":"17","author":"V. V. Zyablov","year":"1981","unstructured":"V. V. Zyablov and M. S. Pinsker. List cascade decoding. Problemy Peredachi Informatsii,17(4):29\u201333, October-December 1981.","journal-title":"Problemy Peredachi Informatsii"}],"container-title":["Lecture Notes in Computer Science","Applied Algebra, Algebraic Algorithms and Error-Correcting Codes"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-45624-4_4","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,1,16]],"date-time":"2025-01-16T21:49:16Z","timestamp":1737064156000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-45624-4_4"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2001]]},"ISBN":["9783540429111","9783540456247"],"references-count":39,"URL":"https:\/\/doi.org\/10.1007\/3-540-45624-4_4","relation":{},"ISSN":["0302-9743"],"issn-type":[{"value":"0302-9743","type":"print"}],"subject":[],"published":{"date-parts":[[2001]]}}}