{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,5,2]],"date-time":"2024-05-02T18:03:56Z","timestamp":1714673036722},"reference-count":53,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2017,1,12]],"date-time":"2017-01-12T00:00:00Z","timestamp":1484179200000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["comput. complex."],"published-print":{"date-parts":[[2017,6]]},"DOI":"10.1007\/s00037-016-0151-x","type":"journal-article","created":{"date-parts":[[2017,1,12]],"date-time":"2017-01-12T16:36:37Z","timestamp":1484238997000},"page":"365-392","update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":6,"title":["List-Decoding Barnes\u2013Wall Lattices"],"prefix":"10.1007","volume":"26","author":[{"given":"Elena","family":"Grigorescu","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Chris","family":"Peikert","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2017,1,12]]},"reference":[{"issue":"1","key":"151_CR1","doi-asserted-by":"publisher","first-page":"60","DOI":"10.1109\/18.817509","volume":"46","author":"Agrawal Dakshi","year":"2000","unstructured":"Dakshi Agrawal, Alexander Vardy (2000) Generalized minimum distance decoding in Euclidean space: Performance analysis. IEEE Transaction on Information Theory 46(1): 60\u201383","journal-title":"IEEE Transaction on Information Theory"},{"key":"151_CR2","doi-asserted-by":"publisher","unstructured":"Adi Akavia, Shafi Goldwasser & Schmuel Safra (2003). Proving Hard-Core Predicates Using List Decoding. In IEEE Symposium on Foundations of Computer Science, 146\u2013157.","DOI":"10.1109\/SFCS.2003.1238189"},{"key":"151_CR3","doi-asserted-by":"publisher","unstructured":"Ian F. Blake Amir H. Banihashemi (1998). Trellis Complexity and Minimal Trellis Diagrams of Lattices. IEEE Transaction on Information Theory 44(5), 1829\u20131847.","DOI":"10.1109\/18.705562"},{"issue":"01","key":"151_CR4","doi-asserted-by":"publisher","first-page":"47","DOI":"10.1017\/S1446788700025064","volume":"1","author":"E. S. Barnes","year":"1959","unstructured":"Barnes E. S., Wall G. E. (1959) Some extreme forms defined in terms of Abelian groups. Journal of the Australian Mathematical Society 1(01): 47\u201363","journal-title":"Journal of the Australian Mathematical Society"},{"key":"151_CR5","unstructured":"Bela Bollob\u00e1s (1986). Combinatorics. Cambridge University Press, Cambridge, U.K"},{"issue":"3","key":"151_CR6","doi-asserted-by":"publisher","first-page":"311","DOI":"10.3934\/amc.2015.9.311","volume":"9","author":"Cohn Henry","year":"2015","unstructured":"Henry Cohn, Nadia Heninger (2015) Ideal forms of Coppersmith\u2019s theorem and Guruswami-Sudan list decoding. Advances in Mathematics of Communications 9(3): 311\u2013339","journal-title":"Advances in Mathematics of Communications"},{"key":"151_CR7","unstructured":"John H. Conway & Neil J. A. Sloane (1998). Sphere Packings, Lattices and Groups. Springer-Verlag, New York."},{"key":"151_CR8","doi-asserted-by":"publisher","unstructured":"Don Coppersmith (2001). Finding Small Solutions to Small Degree Polynomials. In Cryptography and Lattices, International Conference, 20\u201331.","DOI":"10.1007\/3-540-44670-2_3"},{"key":"151_CR9","doi-asserted-by":"publisher","unstructured":"Irit Dinur, Elena Grigorescu, Swastik Kopparty & Madhu Sudan (2008). Decodability of group homomorphisms beyond the Johnson bound. In ACM Symposium on Theory of Computing, 275\u2013284.","DOI":"10.1145\/1374376.1374418"},{"issue":"10","key":"151_CR10","doi-asserted-by":"publisher","first-page":"4488","DOI":"10.1109\/TIT.2008.929014","volume":"54","author":"Dumer Ilya","year":"2008","unstructured":"Ilya Dumer, Gregory Kabatiansky A., C\u00e9dric Tavernier (2008) List Decoding of Biorthogonal Codes and the Hadamard Transform With Linear Complexity. IEEE Transactions on Information Theory 54(10): 4488\u20134492","journal-title":"IEEE Transactions on Information Theory"},{"issue":"1","key":"151_CR11","doi-asserted-by":"publisher","first-page":"258","DOI":"10.1109\/18.817523","volume":"46","author":"Dumer Ilya","year":"2000","unstructured":"Ilya Dumer, Rafail Krichevskiy E. (2000) Soft-decision majority decoding of Reed-Muller codes. IEEE Transactions on Information Theory 46(1): 258\u2013264","journal-title":"IEEE Transactions on Information Theory"},{"issue":"1","key":"151_CR12","doi-asserted-by":"publisher","first-page":"22","DOI":"10.1109\/TIT.2002.806118","volume":"49","author":"Dumer Ilya","year":"2003","unstructured":"Ilya Dumer, Daniele Micciancio, Madhu Sudan (2003) Hardness of approximating the minimum distance of a linear code. IEEE Transaction on Information Theory 49(1): 22\u201337","journal-title":"IEEE Transaction on Information Theory"},{"issue":"2","key":"151_CR13","doi-asserted-by":"publisher","first-page":"253","DOI":"10.1016\/j.dam.2005.05.013","volume":"154","author":"Dumer Ilya","year":"2006","unstructured":"Ilya Dumer, Kirill Shabunov (2006a) Recursive error correction for general Reed-Muller codes. Discrete Applied Mathematics 154(2): 253\u2013269","journal-title":"Discrete Applied Mathematics"},{"issue":"3","key":"151_CR14","doi-asserted-by":"publisher","first-page":"1260","DOI":"10.1109\/TIT.2005.864443","volume":"52","author":"Dumer Ilya","year":"2006","unstructured":"Ilya Dumer, Kirill Shabunov (2006b) Soft-decision decoding of Reed-Muller codes: recursive lists. IEEE Transactions on Information Theory 52(3): 1260\u20131266","journal-title":"IEEE Transactions on Information Theory"},{"key":"151_CR15","unstructured":"Peter Elias (1957). List decoding for noisy channels. Technical Report 335, Research Laboratory of Electronics, MIT."},{"issue":"5","key":"151_CR16","doi-asserted-by":"publisher","first-page":"1152","DOI":"10.1109\/18.21246","volume":"34","author":"G. David Forney","year":"1988","unstructured":"David Forney G. (1988) Coset codes-II: Binary lattices and related codes. IEEE Transactions on Information Theory 34(5): 1152\u20131187","journal-title":"IEEE Transactions on Information Theory"},{"issue":"6","key":"151_CR17","doi-asserted-by":"publisher","first-page":"1992","DOI":"10.1109\/18.556693","volume":"42","author":"G. David Forney","year":"1996","unstructured":"David Forney G., Alexander Vardy (1996) Generalized minimum-distance decoding of Euclidean-space codes and lattices. IEEE Transactions on Information Theory 42(6): 1992\u20132026","journal-title":"IEEE Transactions on Information Theory"},{"issue":"1\u20133","key":"151_CR18","doi-asserted-by":"publisher","first-page":"323","DOI":"10.1007\/s10623-008-9184-8","volume":"49","author":"Fourquet Rafa\u00ebl","year":"2008","unstructured":"Rafa\u00ebl Fourquet, C\u00e9dric Tavernier (2008) An improved list decoding algorithm for the second order Reed-Muller codes and its applications. Designs, Codes and Cryptography 49(1\u20133): 323\u2013340","journal-title":"Designs, Codes and Cryptography"},{"key":"151_CR19","doi-asserted-by":"publisher","unstructured":"Anna C. Gilbert, Sudipto Guha, Piotr Indyk, S. Muthukrishnan & Martin Strauss (2002). Near-optimal sparse Fourier representations via sampling. In ACM Symposium on the Theory of Computing, 152\u2013161.","DOI":"10.1145\/509907.509933"},{"key":"151_CR20","doi-asserted-by":"publisher","unstructured":"Oded Goldreich & Leonid A. Levin (1989). A hard-core predicate for all one-way functions. In In Proceedings of the Twenty First Annual ACM Symposium on Theory of Computing, 25\u201332.","DOI":"10.1145\/73007.73010"},{"issue":"5","key":"151_CR21","doi-asserted-by":"publisher","first-page":"1432","DOI":"10.1137\/090778274","volume":"40","author":"Gopalan Parikshit","year":"2011","unstructured":"Parikshit Gopalan, Venkatesan Guruswami, Prasad Raghavendra (2011) List Decoding Tensor Products and Interleaved Codes. SIAM Journal of Computing 40(5): 1432\u20131462","journal-title":"SIAM Journal of Computing"},{"key":"151_CR22","doi-asserted-by":"publisher","unstructured":"Parikshit Gopalan, Adam R. Klivans & David Zuckerman (2008). List-decoding Reed-Muller codes over small fields. In ACM Symposium on the Theory of Computing, 265\u2013274.","DOI":"10.1145\/1374376.1374417"},{"key":"151_CR23","doi-asserted-by":"publisher","unstructured":"Elena Grigorescu & Chris Peikert (2012). List Decoding Barnes-Wall Lattices. In IEEE Conference on Computational Complexity, 316\u2013325.","DOI":"10.1109\/CCC.2012.33"},{"key":"151_CR24","unstructured":"Venkatesan Guruswami (2004). List Decoding of Error-Correcting Codes (Winning Thesis of the 2002 ACM Doctoral Dissertation Competition), volume 3282 of Lecture Notes in Computer Science. Springer."},{"key":"151_CR25","doi-asserted-by":"publisher","unstructured":"Venkatesan Guruswami (2006). Algorithmic Results in List Decoding. Foundations and Trends in Theoretical Computer Science 2(2).","DOI":"10.1561\/0400000007"},{"key":"151_CR26","unstructured":"Venkatesan Guruswami (2010). Bridging Shannon and Hamming: List Error-Correction with Optimal Rate. ICM Invited Survey."},{"key":"151_CR27","doi-asserted-by":"publisher","unstructured":"Venkatesan Guruswami & Atri Rudra (2006). Explicit capacity-achieving list-decodable codes. In ACM Symposium on the Theory of Computing, 1\u201310.","DOI":"10.1145\/1132516.1132518"},{"key":"151_CR28","doi-asserted-by":"publisher","first-page":"1757","DOI":"10.1109\/18.782097","volume":"45","author":"Guruswami Venkatesan","year":"1999","unstructured":"Venkatesan Guruswami, Madhu Sudan (1999) Improved decoding of Reed-Solomon and Algebraic-geometric codes. IEEE Transactions on Information Theory 45: 1757\u20131767","journal-title":"IEEE Transactions on Information Theory"},{"key":"151_CR29","unstructured":"Venkatesan Guruswami & Madhu Sudan (2001). Extensions to the Johnson Bound. Manuscript. Available from \n                        http:\/\/people.csail.mit.edu\/madhu\/papers\/johnson.ps\n                        \n                    ."},{"key":"151_CR30","doi-asserted-by":"publisher","unstructured":"Venkatesan Guruswami, Christopher Umans & Salil P. Vadhan (2009). Unbalanced expanders and randomness extractors from Parvaresh-Vardy codes. Journal of the ACM 56(4).","DOI":"10.1145\/1538902.1538904"},{"issue":"1","key":"151_CR31","doi-asserted-by":"publisher","first-page":"513","DOI":"10.4086\/toc.2012.v008a023","volume":"8","author":"Haviv Ishay","year":"2012","unstructured":"Ishay Haviv, Oded Regev (2012) Tensor-based Hardness of the Shortest Vector Problem to within Almost Polynomial Factors. Theory of Computing 8(1): 513\u2013531","journal-title":"Theory of Computing"},{"issue":"3","key":"151_CR32","doi-asserted-by":"publisher","first-page":"415","DOI":"10.1287\/moor.12.3.415","volume":"12","author":"Kannan Ravi","year":"1987","unstructured":"Ravi Kannan (1987) Minkowski\u2019s Convex Body Theorem and Integer Programming. Mathematics of Operations Research 12(3): 415\u2013440","journal-title":"Mathematics of Operations Research"},{"key":"151_CR33","unstructured":"Tali Kaufman, Shachar Lovett & Ely Porat (2010). Weight Distribution and List-Decoding Size of Reed- Muller Codes. In Innovations in Computer Science, 422\u2013433."},{"issue":"6","key":"151_CR34","doi-asserted-by":"publisher","first-page":"1331","DOI":"10.1137\/0222080","volume":"22","author":"Kushilevitz Eyal","year":"1993","unstructured":"Eyal Kushilevitz, Yishay Mansour (1993) Learning Decision Trees Using the Fourier Spectrum. SICOMP: SIAM Journal on Computing 22(6): 1331\u20131348","journal-title":"SICOMP: SIAM Journal on Computing"},{"key":"151_CR35","unstructured":"Florence J. MacWilliams & Neil J. A. Sloane (1981). The Theory of Error-Correcting Codes. Elsevier\/North-Holland, Amsterdam."},{"issue":"1","key":"151_CR36","doi-asserted-by":"publisher","first-page":"487","DOI":"10.4086\/toc.2012.v008a022","volume":"8","author":"Micciancio Daniele","year":"2012","unstructured":"Daniele Micciancio (2012) Inapproximability of the Shortest Vector Problem: Toward a Deterministic Reduction. Theory of Computing 8(1): 487\u2013512","journal-title":"Theory of Computing"},{"key":"151_CR37","doi-asserted-by":"publisher","unstructured":"Daniele Micciancio & Shafi Goldwasser (2002). Complexity of Lattice Problems: a cryptographic perspective, volume 671 of The Kluwer International Series in Engineering and Computer Science. Kluwer Academic Publishers, Boston, Massachusetts.","DOI":"10.1007\/978-1-4615-0897-7"},{"key":"151_CR38","doi-asserted-by":"publisher","unstructured":"Daniele Micciancio & Antonio Nicolosi (2008). Efficient Bounded Distance Decoder for Barnes-Wall Lattices. In IEEE International Symposium on Information Theory, 2484\u20132488.","DOI":"10.1109\/ISIT.2008.4595438"},{"key":"151_CR39","first-page":"6","volume":"3","author":"D. E. Muller","year":"1954","unstructured":"Muller D. E. (1954) Application of Boolean algebra to switching circuit design and to error detection. IEEE Transactions on Computers 3: 6\u201312","journal-title":"IEEE Transactions on Computers"},{"key":"151_CR40","doi-asserted-by":"publisher","unstructured":"Gabriele Nebe, Eric M. Rains & Neil J. A. Sloane (2001). The Invariants of the Clifford Groups. Designs, Codes and Cryptography 24(1), 99\u2013122.","DOI":"10.1023\/A:1011233615437"},{"key":"151_CR41","doi-asserted-by":"publisher","unstructured":"Farzad Parvaresh & Alexander Vardy (2005). Correcting Errors Beyond the Guruswami-Sudan Radius in Polynomial Time. In Symposium on Foundations of Computer Science, 285\u2013294. Symposium on Foundations of Computer Science.","DOI":"10.1109\/SFCS.2005.29"},{"issue":"4","key":"151_CR42","doi-asserted-by":"publisher","first-page":"679","DOI":"10.1109\/TIT.2004.825043","volume":"50","author":"Pellikaan Ruud","year":"2004","unstructured":"Ruud Pellikaan, Xin-Wen Wu (2004) List decoding of q-ary Reed-Muller codes. IEEE Transactions on Information Theory 50(4): 679\u2013682","journal-title":"IEEE Transactions on Information Theory"},{"key":"151_CR43","doi-asserted-by":"publisher","unstructured":"Xavier Pujol & Damien Stehl\u00e9 (2008). Rigorous and Efficient Short Lattice Vectors Enumeration. In Advances in Cryptology - ASIACRYPT 2008, 14th International Conference on the Theory and Application of Cryptology and Information Security, 390\u2013405.","DOI":"10.1007\/978-3-540-89255-7_24"},{"key":"151_CR44","doi-asserted-by":"publisher","unstructured":"M. Ran & J. Snyders (1998). Efficient decoding of the Gosset, Coxeter-Todd and the Barnes-Wall lattices. In IEEE International Symposium on Information Theory, 92.","DOI":"10.1109\/ISIT.1998.708678"},{"key":"151_CR45","first-page":"38","volume":"4","author":"Reed S. Irving","year":"1954","unstructured":"Irving Reed S. (1954) A class of multiple-error-correcting codes and the decoding scheme. IEEE Transactions on Information Theory 4: 38\u201349","journal-title":"IEEE Transactions on Information Theory"},{"key":"151_CR46","doi-asserted-by":"publisher","unstructured":"Amir J. Salomon & Ofer Amrani (2005). Augmented product codes and lattices: Reed-Muller codes and Barnes-Wall lattices. IEEE Transactions on Information Theory 51(11), 3918\u20133930.","DOI":"10.1109\/TIT.2005.856937"},{"issue":"1","key":"151_CR47","doi-asserted-by":"publisher","first-page":"180","DOI":"10.1006\/jcom.1997.0439","volume":"13","author":"Sudan Madhu","year":"1997","unstructured":"Madhu Sudan (1997) Decoding of Reed Solomon Codes beyond the Error- Correction Bound. Journal of Complexity 13(1): 180\u2013193","journal-title":"Journal of Complexity"},{"issue":"1","key":"151_CR48","doi-asserted-by":"publisher","first-page":"16","DOI":"10.1145\/346048.346049","volume":"31","author":"Sudan Madhu","year":"2000","unstructured":"Madhu Sudan (2000) List decoding: algorithms and applications. SIGACT News 31(1): 16\u201327","journal-title":"SIGACT News"},{"key":"151_CR49","unstructured":"Madhu Sudan (2001). Algorithmic Introduction to Coding Theory, Lecture Notes. Available from \n                        http:\/\/people.csail.mit.edu\/madhu\/FT01\/\n                        \n                    ."},{"issue":"2","key":"151_CR50","doi-asserted-by":"publisher","first-page":"236","DOI":"10.1006\/jcss.2000.1730","volume":"62","author":"Sudan Madhu","year":"2001","unstructured":"Madhu Sudan, Luca Trevisan, Salil Vadhan P. (2001) Pseudorandom Generators without the XOR Lemma. Journal of Computer and System Sciences 62(2): 236\u2013266","journal-title":"Journal of Computer and System Sciences"},{"key":"151_CR51","doi-asserted-by":"publisher","unstructured":"Amnon Ta-Shma & David Zuckerman (2001). Extractor codes. In ACM Symposium on Theory of Computing, 193\u2013199.","DOI":"10.1145\/380752.380800"},{"issue":"4","key":"151_CR52","doi-asserted-by":"publisher","first-page":"860","DOI":"10.1145\/502090.502099","volume":"48","author":"Trevisan Luca","year":"2001","unstructured":"Luca Trevisan (2001) Extractors and pseudorandom generators. Journal of the ACM 48(4): 860\u2013879","journal-title":"Journal of the ACM"},{"key":"151_CR53","unstructured":"John M. Wozencraft (1958). List Decoding. Quarterly Progress Report, Research Laboratory of Electronics, MIT 48, 90\u201395."}],"container-title":["computational complexity"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00037-016-0151-x\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00037-016-0151-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00037-016-0151-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2017,5,2]],"date-time":"2017-05-02T17:28:11Z","timestamp":1493746091000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00037-016-0151-x"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,1,12]]},"references-count":53,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2017,6]]}},"alternative-id":["151"],"URL":"https:\/\/doi.org\/10.1007\/s00037-016-0151-x","relation":{},"ISSN":["1016-3328","1420-8954"],"issn-type":[{"value":"1016-3328","type":"print"},{"value":"1420-8954","type":"electronic"}],"subject":[],"published":{"date-parts":[[2017,1,12]]}}}