{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,11,11]],"date-time":"2026-11-11T07:11:11Z","timestamp":1794381071515,"version":"4.9.0"},"publisher-location":"Berlin, Heidelberg","reference-count":15,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783540228493","type":"print"},{"value":"9783540278368","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2004]]},"DOI":"10.1007\/978-3-540-27836-8_59","type":"book-chapter","created":{"date-parts":[[2010,9,15]],"date-time":"2010-09-15T18:53:21Z","timestamp":1284576801000},"page":"695-707","source":"Crossref","is-referenced-by-count":16,"title":["Linear-Time List Decoding in Error-Free Settings"],"prefix":"10.1007","author":[{"given":"Venkatesan","family":"Guruswami","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Piotr","family":"Indyk","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","reference":[{"issue":"6","key":"59_CR1","doi-asserted-by":"publisher","first-page":"1737","DOI":"10.1109\/18.556670","volume":"42","author":"A. Albanese","year":"1996","unstructured":"Albanese, A., Blomer, J., Edmonds, J., Luby, M., Sudan, M.: Priority encoding transmission. IEEE Transactions on Information Theory\u00a042(6), 1737\u20131744 (1996)","journal-title":"IEEE Transactions on Information Theory"},{"key":"59_CR2","doi-asserted-by":"crossref","unstructured":"Alekhnovich, M.: Linear diophantine equations over polynomials and soft decoding of Reed-Solomon codes. In: Proceedings of the Symposium on Foundations of Computer Science, pp. 439\u2013448 (2002)","DOI":"10.1109\/SFCS.2002.1181968"},{"key":"59_CR3","doi-asserted-by":"publisher","first-page":"509","DOI":"10.1109\/18.119713","volume":"38","author":"N. Alon","year":"1992","unstructured":"Alon, N., Bruck, J., Naor, J., Naor, M., Roth, R.: Construction of asymptotically good low-rate error-correcting codes through pseudo-random graphs. IEEE Transactions on Information Theory\u00a038, 509\u2013516 (1992)","journal-title":"IEEE Transactions on Information Theory"},{"key":"59_CR4","doi-asserted-by":"crossref","unstructured":"Alon, N., Edmonds, J., Luby, M.: Linear time erasure codes with nearly optimal recovery. In: Proceedings of the 36th IEEE Symposium on Foundations of Computer Science, pp. 512\u2013519 (1995)","DOI":"10.1109\/SFCS.1995.492581"},{"issue":"2","key":"59_CR5","doi-asserted-by":"crossref","first-page":"487","DOI":"10.1080\/03610919908813561","volume":"28","author":"A. Sigal","year":"1999","unstructured":"Sigal, A., Lipton, R.J., Rubinfeld, R., Sudan, M.: Reconstructing algebraic functions from mixed data. SIAM Journal on Computing\u00a028(2), 487\u2013510 (1999)","journal-title":"SIAM Journal on Computing"},{"key":"59_CR6","first-page":"88","volume":"48","author":"P. Elias","year":"1958","unstructured":"Elias, P.: Zero error capacity under list decoding. Quarterly Progress Report, Research Laboratory of Electronics\u00a048, 88\u201390 (1958)","journal-title":"Quarterly Progress Report, Research Laboratory of Electronics"},{"key":"59_CR7","unstructured":"Feng, G.L.: Two fast algorithms in the Sudan decoding procedure. In: Proceedings of the 37th Annual Allerton Conference on Communication, Control and Computing, pp. 545\u2013554 (1999)"},{"issue":"11","key":"59_CR8","doi-asserted-by":"publisher","first-page":"2826","DOI":"10.1109\/TIT.2003.815776","volume":"49","author":"V. Guruswami","year":"2003","unstructured":"Guruswami, V.: List decoding from erasures: Bounds and code constructions. IEEE Transactions on Information Theory\u00a049(11), 2826\u20132833 (2003)","journal-title":"IEEE Transactions on Information Theory"},{"key":"59_CR9","doi-asserted-by":"crossref","unstructured":"Guruswami, V., Indyk, P.: Near-optimal linear-time codes for unique decoding and new list-decodable codes over smaller alphabets. In: Proceedings of the Symposium on Theory of Computing, pp. 812\u2013821 (2002)","DOI":"10.1145\/509907.510023"},{"key":"59_CR10","doi-asserted-by":"crossref","unstructured":"Guruswami, V., Indyk, P.: Linear-time encodable and list-decodable codes. In: Proceedings of the Symposium on Theory of Computing, pp. 126\u2013135 (2003)","DOI":"10.1145\/780542.780562"},{"key":"59_CR11","doi-asserted-by":"publisher","first-page":"1757","DOI":"10.1109\/18.782097","volume":"45","author":"V. Guruswami","year":"1999","unstructured":"Guruswami, V., Sudan, M.: Improved decoding of Reed-Solomon and algebraic-geometric codes. IEEE Transactions on Information Theory\u00a045, 1757\u20131767 (1999)","journal-title":"IEEE Transactions on Information Theory"},{"issue":"3","key":"59_CR12","doi-asserted-by":"publisher","first-page":"261","DOI":"10.1007\/BF02126799","volume":"8","author":"A. Lubotzky","year":"1988","unstructured":"Lubotzky, A., Phillips, R., Sarnak, P.: Ramanujan graphs. Combinatorica\u00a08(3), 261\u2013277 (1988)","journal-title":"Combinatorica"},{"issue":"6","key":"59_CR13","doi-asserted-by":"publisher","first-page":"1723","DOI":"10.1109\/18.556668","volume":"42","author":"D. Spielman","year":"1996","unstructured":"Spielman, D.: Linear-time encodable and decodable error-correcting codes. IEEE Transactions on Information Theory\u00a042(6), 1723\u20131732 (1996)","journal-title":"IEEE Transactions on Information Theory"},{"issue":"1","key":"59_CR14","doi-asserted-by":"publisher","first-page":"180","DOI":"10.1006\/jcom.1997.0439","volume":"13","author":"M. Sudan","year":"1997","unstructured":"Sudan, M.: Decoding of Reed-Solomon codes beyond the error-correction bound. Journal of Complexity\u00a013(1), 180\u2013193 (1997)","journal-title":"Journal of Complexity"},{"issue":"2","key":"59_CR15","doi-asserted-by":"publisher","first-page":"835","DOI":"10.1109\/18.910593","volume":"47","author":"G. Z\u00e9mor","year":"2001","unstructured":"Z\u00e9mor, G.: On expander codes. IEEE Transactions on Information Theory\u00a047(2), 835\u2013837 (2001)","journal-title":"IEEE Transactions on Information Theory"}],"container-title":["Lecture Notes in Computer Science","Automata, Languages and Programming"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-27836-8_59.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,5,2]],"date-time":"2021-05-02T23:31:03Z","timestamp":1619998263000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-27836-8_59"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2004]]},"ISBN":["9783540228493","9783540278368"],"references-count":15,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-27836-8_59","relation":{"is-part-of":[{"id-type":"doi","id":"https:\/\/doi.org\/10.1007\/b99859","asserted-by":"object"}]},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2004]]}}}