{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,11]],"date-time":"2026-06-11T10:05:56Z","timestamp":1781172356098,"version":"3.54.1"},"publisher-location":"Berlin, Heidelberg","reference-count":34,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783540678236","type":"print"},{"value":"9783540449294","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2000]]},"DOI":"10.1007\/3-540-44929-9_3","type":"book-chapter","created":{"date-parts":[[2007,5,5]],"date-time":"2007-05-05T13:20:53Z","timestamp":1178371253000},"page":"25-41","source":"Crossref","is-referenced-by-count":15,"title":["List Decoding: Algorithms and Applications"],"prefix":"10.1007","author":[{"given":"Madhu","family":"Sudan","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2001,8,24]]},"reference":[{"key":"3_CR1","doi-asserted-by":"crossref","unstructured":"Werner Alexi, Benny Chor, Oded Goldreich, and Claus P. Schnorr. RSA and Rabin functions: Certain parts are as hard as the whole. SIAM Journal on Computing, 17(2):194\u2013209, April1988.","DOI":"10.1137\/0217013"},{"key":"3_CR2","doi-asserted-by":"crossref","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.","DOI":"10.1137\/S0097539796297577"},{"key":"3_CR3","doi-asserted-by":"crossref","unstructured":"Sanjeev Arora and Madhu Sudan. Improved low degree testing and its applications. In Proceedings of the Twenty-Ninth Annual ACM Symposium on Theory of Computing, pages 485\u2013495, El Paso, Texas, 4\u20136 May 1997.","DOI":"10.1145\/258533.258642"},{"issue":"4","key":"3_CR4","doi-asserted-by":"publisher","first-page":"307","DOI":"10.1007\/BF01275486","volume":"3","author":"L. Babai","year":"1993","unstructured":"L\u00e1szl\u00f3 Babai, Lance Fortnow, Noam Nisan, and Avi Wigderson. BPP has subexponential time simulations unless EXPTIME has publishable proofs. Computational Complexity, 3(4):307\u2013318, 1993.","journal-title":"Computational Complexity"},{"key":"3_CR5","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"37","DOI":"10.1007\/3-540-52282-4_30","volume-title":"7th Annual Symposium on Theoretical Aspects of Computer Science","author":"D. Beaver","year":"1990","unstructured":"Donald Beaver and Joan Feigenbaum. Hiding instances in multioracle queries. In 7th Annual Symposium on Theoretical Aspects of Computer Science, volume 415 of Lecture Notes in Computer Science, pages 37\u201348, Rouen, France, 22\u201324 February 1990. Springer."},{"issue":"4","key":"3_CR6","doi-asserted-by":"crossref","first-page":"850","DOI":"10.1137\/0213053","volume":"13","author":"Manuel Blum and Silvio Micali","year":"1984","unstructured":"Manuel Blum and Silvio Micali. How to generate cryptographically strong sequences of pseudo-random bits. SIAM Journal on Computing, 13(4):850\u2013864, November 1984.","journal-title":"SIAM Journal on Computing"},{"key":"3_CR7","doi-asserted-by":"crossref","unstructured":"Dan Boneh. Finding smooth integers in short intervals using CRT decoding. (To appear) Proceedings of the Thirty-Second Annual ACM Symposium on Theory of Computing, Portland, Oregon, 21\u201323 May 2000.","DOI":"10.1145\/335305.335337"},{"key":"3_CR8","series-title":"Lect Notes Comput Sci","volume-title":"16th International Symposium on Theoretical Aspects of Computer Science","author":"J.-Y. Cai","year":"1999","unstructured":"Jin-Yi Cai, A. Pavan, and D. Sivakumar. On the hardness of the permanent. In 16th International Symposium on Theoretical Aspects of Computer Science, Lecture Notes in Computer Science, Trier, Germany, March 4\u20136 1999. Springer-Verlag."},{"key":"3_CR9","unstructured":"Peter Elias. List decoding for noisy channels. In 1957-IRE WESCON Convention Record, Pt. 2, pages 94\u2013104, 1957."},{"key":"3_CR10","doi-asserted-by":"crossref","unstructured":"Joan Feigenbaum. The use of coding theory in computational complexity. In Proceedings of Symposia in Applied Mathematics, R. Calderbank (ed.), American Mathematics Society, Providence, pages 203\u2013229, 1995.","DOI":"10.1090\/psapm\/050\/1368642"},{"key":"3_CR11","doi-asserted-by":"crossref","unstructured":"Anna Gal, Shai Halevi, Richard Lipton, and Erez Petrank. Computing from partial solutions In Proceedings of the Fourteenth Annual IEEE Conference on Computational Complexity, Atlanta, Georgia, 4\u20136 May 1999.","DOI":"10.1109\/CCC.1999.766260"},{"key":"3_CR12","doi-asserted-by":"crossref","unstructured":"Oded Goldreich and Leonid A. Levin. A hard-core predicate for all one-way functions. In Proceedings of the Twenty First Annual ACM Symposium on Theory of Computing, pages 25\u201332, Seattle, Washington, 15\u201317 May 1989.","DOI":"10.1145\/73007.73010"},{"key":"3_CR13","unstructured":"Oded Goldreich, Ronitt Rubinfeld, and Madhu Sudan. Learning polynomials with queries\u2014the highly noisy case. Technical Report TR98-060, Electronic Colloquium on Computational Complexity, 1998. Preliminary version in FOCS\u2019 95."},{"key":"3_CR14","doi-asserted-by":"crossref","unstructured":"Oded Goldreich, Dana Ron, and Madhu Sudan. Chinese remaindering with errors. Proceedings of the Thirty-First Annual ACM Symposium on Theory of Computing, pages 225\u2013234, Atlanta, Georgia, 1\u20134 May 1999.","DOI":"10.1145\/301250.301309"},{"key":"3_CR15","unstructured":"Venkatesan Guruswami, Johan H\u00e5stad, Madhu Sudan, and David Zuckerman. Untitled Manuscript, January 2000."},{"key":"3_CR16","unstructured":"Venkatesan Guruswami, Amit Sahai, and Madhu Sudan. Untitled Manuscript, January 2000."},{"issue":"6","key":"3_CR17","doi-asserted-by":"crossref","first-page":"1757","DOI":"10.1109\/18.782097","volume":"45","author":"Venkatesan Guruswami and Madhu Sudan","year":"1999","unstructured":"Venkatesan Guruswami and Madhu Sudan. Improved decoding of Reed-Solomon and algebraic-geometric codes. IEEE Transactions on Information Theory, 45(6): 1757\u20131767, September 1999.","journal-title":"IEEE Transactions on Information Theory"},{"key":"3_CR18","unstructured":"Venkatesan Guruswami and Madhu Sudan, Low-rate codes with high error correction capabilities. (To appear) Proceedings of the Thirty-Second Annual ACM Symposium on Theory of Computing, Portland, Oregon, 21\u201323 May 2000."},{"key":"3_CR19","unstructured":"Russell Impagliazzo. Personal Communication, July 1997."},{"key":"3_CR20","doi-asserted-by":"crossref","unstructured":"Russell Impagliazzo. Hard-core distributions for somewhat hard problems. In 36th Annual Symposium on Foundations of Computer Science, pages 538\u2013545, Milwaukee, Wisconsin, 23\u201325 October 1995. IEEE.","DOI":"10.1109\/SFCS.1995.492584"},{"key":"3_CR21","doi-asserted-by":"crossref","unstructured":"Russell Impagliazzo, Ronen Shaltiel, and Avi Wigderson. Near-optimal conversion of hardness into pseudo-randomness. In Proceedings of the Thirty-Ninth Annual IEEE Symposium on Foundations of Computer Science, New York City, New York, 17\u201319 October 1999. (To appear.)","DOI":"10.1109\/SFFCS.1999.814590"},{"key":"3_CR22","doi-asserted-by":"crossref","unstructured":"Russell Impagliazzo and Avi Wigderson. P = BPP if E requires exponential circuits: Derandomizing the XOR lemma. In Proceedings of the Twenty-Ninth Annual ACM Symposium on Theory of Computing, pages 220\u2013229, El Paso, Texas, 4\u20136 May 1997.","DOI":"10.1145\/258533.258590"},{"key":"3_CR23","doi-asserted-by":"crossref","unstructured":"Erich Kaltofen. Polynomial factorization 1987\u20131991. In I. Simon, editor, Proc. LATIN\u2019 92, volume 583 of Lect. Notes Comput. Sci., pages 294\u2013313, Heidelberg, Germany, 1992. Springer Verlag.","DOI":"10.1007\/BFb0023837"},{"key":"3_CR24","unstructured":"S. Ravi Kumar and D. Sivakumar. Proofs, codes, and polynomial-time reducibilities. In Proceedings of the Fourteenth Annual IEEE Conference on Computational Complexity, Atlanta, Georgia, 4\u20136 May 1999."},{"key":"3_CR25","unstructured":"Richard Lipton. New directions in testing. In Proceedings of DIMACS Workshop on Distributed Computing and Cryptography, 1989."},{"issue":"2","key":"3_CR26","doi-asserted-by":"crossref","first-page":"149","DOI":"10.1016\/S0022-0000(05)80043-1","volume":"49","author":"Noam Nisan and Avi Wigderson","year":"1994","unstructured":"Noam Nisan and Avi Wigderson. Hardness vs randomness. Journal of Computer and System Sciences, 49(2):149\u2013167, October 1994.","journal-title":"Journal of Computer and System Sciences"},{"key":"3_CR27","unstructured":"Vera Pless, W. Cary Huffman, and Richard A. Brualdi (Eds.). Handbook of Coding Theory, North-Holland, 1998."},{"key":"3_CR28","doi-asserted-by":"crossref","unstructured":"Ran Raz, Omer Reingold, and Salil Vadhan. Extracting all the randomness and reducing the error in Trevisan\u2019s extractors. In Proceedings of the 31st Annual ACM Symposium on the Theory of Computing, Atlanta, GA, May 1999.","DOI":"10.1145\/301250.301292"},{"key":"3_CR29","doi-asserted-by":"crossref","first-page":"432","DOI":"10.1109\/18.748993","volume":"45","author":"M. Amin Shokrollahi","year":"1999","unstructured":"M. Amin Shokrollahi and Hal Wasserman. List decoding of algebraic-geometric codes IEEE Transactions on Information Theory, 45:432\u2013437, March 1999.","journal-title":"IEEE Transactions on Information Theory"},{"issue":"2","key":"3_CR30","doi-asserted-by":"crossref","first-page":"270","DOI":"10.1006\/jcss.1999.1653","volume":"59","author":"D. Sivakumar","year":"1999","unstructured":"D. Sivakumar. On membership comparable sets. Journal of Computer and System Sciences, 59(2): 270\u2013280, October 1999.","journal-title":"Journal of Computer and System Sciences"},{"issue":"1","key":"3_CR31","doi-asserted-by":"crossref","first-page":"180","DOI":"10.1006\/jcom.1997.0439","volume":"13","author":"Madhu Sudan","year":"1997","unstructured":"Madhu Sudan. Decoding of Reed Solomon codes beyond the error-correction bound. Journal of Complexity, 13(1):180\u2013193, March 1997.","journal-title":"Journal of Complexity"},{"key":"3_CR32","doi-asserted-by":"crossref","unstructured":"Madhu Sudan, Luca Trevisan, and Salil Vadhan. Pseudorandom generators without the XOR lemma [extended abstract]. In Proceedings of the Thirty-First Annual ACM Symposium on the Theory of Computing, pages 537\u2013546, Atlanta, Georgia, 1\u20134 May 1999.","DOI":"10.1145\/301250.301397"},{"key":"3_CR33","unstructured":"Amnon Ta-Shma and David Zuckerman. Personal communication, November 1999."},{"key":"3_CR34","doi-asserted-by":"crossref","unstructured":"Luca Trevisan. Construction of extractors using pseudorandom generators. In Proceedings of the Thirty-First Annual ACM Symposium on the Theory of Computing, Atlanta, Georgia, 1\u20134 May 1999.","DOI":"10.1145\/301250.301289"}],"container-title":["Lecture Notes in Computer Science","Theoretical Computer Science: Exploring New Frontiers of Theoretical Informatics"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-44929-9_3","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,4,27]],"date-time":"2019-04-27T18:40:58Z","timestamp":1556390458000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-44929-9_3"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2000]]},"ISBN":["9783540678236","9783540449294"],"references-count":34,"URL":"https:\/\/doi.org\/10.1007\/3-540-44929-9_3","relation":{},"ISSN":["0302-9743"],"issn-type":[{"value":"0302-9743","type":"print"}],"subject":[],"published":{"date-parts":[[2000]]}}}