{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,4]],"date-time":"2026-04-04T21:15:06Z","timestamp":1775337306030,"version":"3.50.1"},"publisher-location":"Berlin, Heidelberg","reference-count":31,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783662476710","type":"print"},{"value":"9783662476727","type":"electronic"}],"license":[{"start":{"date-parts":[[2015,1,1]],"date-time":"2015-01-01T00:00:00Z","timestamp":1420070400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2015,1,1]],"date-time":"2015-01-01T00:00:00Z","timestamp":1420070400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2015]]},"DOI":"10.1007\/978-3-662-47672-7_57","type":"book-chapter","created":{"date-parts":[[2015,6,19]],"date-time":"2015-06-19T10:07:39Z","timestamp":1434708459000},"page":"701-712","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":9,"title":["Linear-Time List Recovery of High-Rate Expander Codes"],"prefix":"10.1007","author":[{"given":"Brett","family":"Hemenway","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Mary","family":"Wootters","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2015,6,20]]},"reference":[{"issue":"6","key":"57_CR1","doi-asserted-by":"publisher","first-page":"1732","DOI":"10.1109\/18.556669","volume":"42","author":"N Alon","year":"1996","unstructured":"Alon, N., Luby, M.: A linear time erasure-resilient code with nearly optimal recovery. IEEE Transactions on Information Theory 42(6), 1732\u20131736 (1996)","journal-title":"IEEE Transactions on Information Theory"},{"issue":"6","key":"57_CR2","doi-asserted-by":"publisher","first-page":"1725","DOI":"10.1109\/TIT.2002.1003853","volume":"48","author":"A Barg","year":"2002","unstructured":"Barg, A., Zemor, G.: Error exponents of expander codes. IEEE Transactions on Information Theory 48(6), 1725\u20131729 (2002)","journal-title":"IEEE Transactions on Information Theory"},{"issue":"5","key":"57_CR3","doi-asserted-by":"publisher","first-page":"1625","DOI":"10.1109\/TIT.2005.846392","volume":"51","author":"A Barg","year":"2005","unstructured":"Barg, A., Zemor, G.: Concatenated codes: serial and parallel. IEEE Transactions on Information Theory 51(5), 1625\u20131634 (2005)","journal-title":"IEEE Transactions on Information Theory"},{"issue":"1","key":"57_CR4","doi-asserted-by":"publisher","first-page":"78","DOI":"10.1109\/TIT.2005.860415","volume":"52","author":"A Barg","year":"2006","unstructured":"Barg, A., Zemor, G.: Distance properties of expander codes. IEEE Transactions on Information Theory 52(1), 78\u201390 (2006)","journal-title":"IEEE Transactions on Information Theory"},{"key":"57_CR5","doi-asserted-by":"crossref","unstructured":"Dvir, Z., Lovett, S.: Subspace evasive sets. In: Proceedings of the 44th Annual ACM Symposium on Theory of Computing (STOC), pp. 351\u2013358. ACM (2012)","DOI":"10.1145\/2213977.2214010"},{"key":"57_CR6","doi-asserted-by":"crossref","unstructured":"Gallager, R.G.: Low Density Parity-Check Codes. Technical report. MIT (1963)","DOI":"10.7551\/mitpress\/4347.001.0001"},{"key":"57_CR7","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"461","DOI":"10.1007\/978-3-642-39206-1_39","volume-title":"Automata, Languages, and Programming","author":"AC Gilbert","year":"2013","unstructured":"Gilbert, A.C., Ngo, H.Q., Porat, E., Rudra, A., Strauss, M.J.: $$\\ell $$\n                  $$_\\text{2 }$$\/$$\\ell $$\n                  $$_\\text{2 }$$-foreach sparse recovery with low risk. In: Fomin, F.V., Freivalds, R., Kwiatkowska, M., Peleg, D. (eds.) ICALP 2013, Part I. LNCS, vol. 7965, pp. 461\u2013472. Springer, Heidelberg (2013)"},{"issue":"11","key":"57_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 49(11), 2826\u20132833 (2003)","journal-title":"IEEE Transactions on Information Theory"},{"key":"57_CR9","series-title":"Lecture Notes in Computer Science","volume-title":"List decoding of error-correcting codes: winning thesis of the 2002 ACM doctoral dissertation competition","author":"V Guruswami","year":"2004","unstructured":"Guruswami, V.: List decoding of error-correcting codes. LNCS, vol. 3282. Springer, Heidelberg (2004)"},{"key":"57_CR10","doi-asserted-by":"crossref","unstructured":"Guruswami, V.: Linear-algebraic list decoding of folded reed-solomon codes. In: Proceedings of the 26th Annual Conference on Computational Complexity (CCC), pp. 77\u201385. IEEE (2011)","DOI":"10.1109\/CCC.2011.22"},{"key":"57_CR11","doi-asserted-by":"crossref","unstructured":"Guruswami, V., Indyk, P:. Expander-based constructions of efficiently decodable codes. In: Proceedings of the 42nd Annual IEEE Symposium on Foundations of Computer Science (FOCS), pp. 658\u2013667. IEEE (October 2001)","DOI":"10.1109\/SFCS.2001.959942"},{"key":"57_CR12","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 34th Annual ACM Aymposium on Theory of computing (STOC), pp. 812\u2013821. ACM (2002)","DOI":"10.1145\/509907.510023"},{"key":"57_CR13","doi-asserted-by":"crossref","unstructured":"Guruswami, V., Indyk, P.: Linear time encodable and list decodable codes. In: Proceedings of the 35th Annual ACM Symposium on Theory of Computing (STOC), pp. 126\u2013135. ACM, New York (2003)","DOI":"10.1145\/780542.780562"},{"key":"57_CR14","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"695","DOI":"10.1007\/978-3-540-27836-8_59","volume-title":"Automata, Languages and Programming","author":"V Guruswami","year":"2004","unstructured":"Guruswami, V., Indyk, P.: Linear-time list decoding in error-free settings. In: D\u00edaz, J., Karhum\u00e4ki, J., Lepist\u00f6, A., Sannella, D. (eds.) ICALP 2004. LNCS, vol. 3142, pp. 695\u2013707. Springer, Heidelberg (2004)"},{"key":"57_CR15","doi-asserted-by":"crossref","unstructured":"Guruswami, V., Kopparty, S.: Explicit subspace designs. In: Proceedings of the 54th Annual IEEE Symposium on Foundations of Computing (FOCS), pp. 608\u2013617. IEEE (2013)","DOI":"10.1109\/FOCS.2013.71"},{"issue":"1","key":"57_CR16","doi-asserted-by":"publisher","first-page":"135","DOI":"10.1109\/TIT.2007.911222","volume":"54","author":"V Guruswami","year":"2008","unstructured":"Guruswami, V., Rudra, A.: Explicit codes achieving list decoding capacity: Error-correction with optimal redundancy. IEEE Transactions on Information Theory 54(1), 135\u2013150 (2008)","journal-title":"IEEE Transactions on Information Theory"},{"key":"57_CR17","doi-asserted-by":"crossref","unstructured":"Guruswami, V., Sudan, M.: Improved decoding of Reed-Solomon and algebraic-geometry codes. IEEE Transactions on Information Theory 45(6) (1999)","DOI":"10.1109\/18.782097"},{"key":"57_CR18","doi-asserted-by":"crossref","unstructured":"Guruswami, V., Xing, C.: Folded codes from function field towers and improved optimal rate list decoding. In: Proceedings of the 44th Annual ACM Symposium on Theory of Computing (STOC), pp. 339\u2013350. ACM (2012)","DOI":"10.1145\/2213977.2214009"},{"key":"57_CR19","doi-asserted-by":"crossref","unstructured":"Guruswami, V., Xing, C.: List decoding reed-solomon, algebraic-geometric, and gabidulin subcodes up to the singleton bound. In: Proceedings of the 45th Annual ACM Symposium on Theory of Computing (STOC), pp. 843\u2013852. ACM (2013)","DOI":"10.1145\/2488608.2488715"},{"key":"57_CR20","doi-asserted-by":"crossref","unstructured":"Hemenway, B., Ostrovsky, R., Wootters, M.: Local correctability of expander codes. Information and Computation (2014)","DOI":"10.1007\/978-3-642-39206-1_46"},{"key":"57_CR21","doi-asserted-by":"crossref","unstructured":"Hemenway, B., Wootters, M.: Linear-time list recovery of high-rate expander codes. ArXiv preprint 1503.01955 (2015)","DOI":"10.1007\/978-3-662-47672-7_57"},{"issue":"4","key":"57_CR22","doi-asserted-by":"publisher","first-page":"439","DOI":"10.1090\/S0273-0979-06-01126-8","volume":"43","author":"S Hoory","year":"2006","unstructured":"Hoory, S., Linial, N., Wigderson, A.: Expander graphs and their applications. Bulletin of the American Mathematical Society 43(4), 439\u2013561 (2006)","journal-title":"Bulletin of the American Mathematical Society"},{"key":"57_CR23","doi-asserted-by":"crossref","unstructured":"Indyk, P., Ngo, H.Q., Rudra, A.: Efficiently decodable non-adaptive group testing. In: Proceedings of the 21st Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 1126\u20131142. Society for Industrial and Applied Mathematics (2010)","DOI":"10.1137\/1.9781611973075.91"},{"issue":"3","key":"57_CR24","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 8(3), 261\u2013277 (1988)","journal-title":"Combinatorica"},{"issue":"1","key":"57_CR25","first-page":"51","volume":"24","author":"GA Margulis","year":"1988","unstructured":"Margulis, G.A.: Explicit Group-Theoretical Constructions of Combinatorial Schemes and Their Application to the Design of Expanders and Concentrators. Probl. Peredachi Inf. 24(1), 51\u201360 (1988)","journal-title":"Probl. Peredachi Inf."},{"key":"57_CR26","unstructured":"Meir, O.: Locally correctable and testable codes approaching the singleton bound, ECCC Report TR14-107 (2014)"},{"issue":"1","key":"57_CR27","doi-asserted-by":"publisher","first-page":"44","DOI":"10.1006\/jctb.1994.1054","volume":"62","author":"M Morgenstern","year":"1994","unstructured":"Morgenstern, M.: Existence and Explicit Constructions of q + 1 Regular Ramanujan Graphs for Every Prime Power q. Journal of Combinatorial Theory, Series B 62(1), 44\u201362 (1994)","journal-title":"Journal of Combinatorial Theory, Series B"},{"key":"57_CR28","unstructured":"Ngo, H.Q., Porat, E., Rudra, A.: Efficiently decodable compressed sensing by list-recoverable codes and recursion. In: Proceedings of the Symposium on Theoretical Aspects of Computer Science (STACS), vol. 14, pp. 230\u2013241 (2012)"},{"key":"57_CR29","doi-asserted-by":"crossref","unstructured":"Sipser, M., Spielman, D.A.: Expander codes. IEEE Transactions in Information Theory 42(6) (1996)","DOI":"10.1109\/18.556667"},{"issue":"5","key":"57_CR30","doi-asserted-by":"publisher","first-page":"533","DOI":"10.1109\/TIT.1981.1056404","volume":"27","author":"R Tanner","year":"1981","unstructured":"Tanner, R.: A recursive approach to low complexity codes. IEEE Transactions on Information Theory 27(5), 533\u2013547 (1981)","journal-title":"IEEE Transactions on Information Theory"},{"issue":"2","key":"57_CR31","doi-asserted-by":"publisher","first-page":"835","DOI":"10.1109\/18.910593","volume":"47","author":"G Zemor","year":"2001","unstructured":"Zemor, G.: On expander codes. IEEE Transactions on Information Theory 47(2), 835\u2013837 (2001)","journal-title":"IEEE Transactions on Information Theory"}],"container-title":["Lecture Notes in Computer Science","Automata, Languages, and Programming"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-662-47672-7_57","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,2,10]],"date-time":"2023-02-10T08:44:54Z","timestamp":1676018694000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-662-47672-7_57"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015]]},"ISBN":["9783662476710","9783662476727"],"references-count":31,"URL":"https:\/\/doi.org\/10.1007\/978-3-662-47672-7_57","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2015]]},"assertion":[{"value":"20 June 2015","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}