Abstract
The question of list-decoding error-correcting codes over finite fields (under the Hamming metric) has been widely studied in recent years. Motivated by the similar discrete linear structure of linear codes and point lattices in \({\mathbb{R}^{N}}\), and their many shared applications across complexity theory, cryptography, and coding theory, we initiate the study of list decoding for lattices. Namely: for a lattice \({\mathcal{L}\subseteq \mathbb{R}^N}\), given a target vector \({r \in \mathbb{R}^N}\) and a distance parameter d, output the set of all lattice points \({w \in \mathcal{L}}\) that are within distance d of r.
In this work, we focus on combinatorial and algorithmic questions related to list decoding for the well-studied family of Barnes–Wall lattices. Our main contributions are twofold:
-
1.
We give tight combinatorial bounds on the worst-case list size, showing it to be polynomial in the lattice dimension for any error radius bounded away from the lattice’s minimum distance (in the Euclidean norm).
-
2.
We use our combinatorial bounds to generalize the unique-decoding algorithm of Micciancio and Nicolosi (IEEE International Symposium on Information Theory 2008) to work beyond the unique-decoding radius and still run in polynomial time up to the list-decoding radius. Just like the Micciancio–Nicolosi algorithm, our algorithm is highly parallelizable, and with sufficiently many processors, it can run in parallel time only poly-logarithmic in the lattice dimension.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Dakshi Agrawal, Alexander Vardy (2000) Generalized minimum distance decoding in Euclidean space: Performance analysis. IEEE Transaction on Information Theory 46(1): 60–83
Adi Akavia, Shafi Goldwasser & Schmuel Safra (2003). Proving Hard-Core Predicates Using List Decoding. In IEEE Symposium on Foundations of Computer Science, 146–157.
Ian F. Blake Amir H. Banihashemi (1998). Trellis Complexity and Minimal Trellis Diagrams of Lattices. IEEE Transaction on Information Theory 44(5), 1829–1847.
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–63
Bela Bollobás (1986). Combinatorics. Cambridge University Press, Cambridge, U.K
Henry Cohn, Nadia Heninger (2015) Ideal forms of Coppersmith’s theorem and Guruswami-Sudan list decoding. Advances in Mathematics of Communications 9(3): 311–339
John H. Conway & Neil J. A. Sloane (1998). Sphere Packings, Lattices and Groups. Springer-Verlag, New York.
Don Coppersmith (2001). Finding Small Solutions to Small Degree Polynomials. In Cryptography and Lattices, International Conference, 20–31.
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–284.
Ilya Dumer, Gregory Kabatiansky A., Cédric Tavernier (2008) List Decoding of Biorthogonal Codes and the Hadamard Transform With Linear Complexity. IEEE Transactions on Information Theory 54(10): 4488–4492
Ilya Dumer, Rafail Krichevskiy E. (2000) Soft-decision majority decoding of Reed-Muller codes. IEEE Transactions on Information Theory 46(1): 258–264
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–37
Ilya Dumer, Kirill Shabunov (2006a) Recursive error correction for general Reed-Muller codes. Discrete Applied Mathematics 154(2): 253–269
Ilya Dumer, Kirill Shabunov (2006b) Soft-decision decoding of Reed-Muller codes: recursive lists. IEEE Transactions on Information Theory 52(3): 1260–1266
Peter Elias (1957). List decoding for noisy channels. Technical Report 335, Research Laboratory of Electronics, MIT.
David Forney G. (1988) Coset codes-II: Binary lattices and related codes. IEEE Transactions on Information Theory 34(5): 1152–1187
David Forney G., Alexander Vardy (1996) Generalized minimum-distance decoding of Euclidean-space codes and lattices. IEEE Transactions on Information Theory 42(6): 1992–2026
Rafaël Fourquet, Cédric Tavernier (2008) An improved list decoding algorithm for the second order Reed-Muller codes and its applications. Designs, Codes and Cryptography 49(1–3): 323–340
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–161.
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–32.
Parikshit Gopalan, Venkatesan Guruswami, Prasad Raghavendra (2011) List Decoding Tensor Products and Interleaved Codes. SIAM Journal of Computing 40(5): 1432–1462
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–274.
Elena Grigorescu & Chris Peikert (2012). List Decoding Barnes-Wall Lattices. In IEEE Conference on Computational Complexity, 316–325.
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.
Venkatesan Guruswami (2006). Algorithmic Results in List Decoding. Foundations and Trends in Theoretical Computer Science 2(2).
Venkatesan Guruswami (2010). Bridging Shannon and Hamming: List Error-Correction with Optimal Rate. ICM Invited Survey.
Venkatesan Guruswami & Atri Rudra (2006). Explicit capacity-achieving list-decodable codes. In ACM Symposium on the Theory of Computing, 1–10.
Venkatesan Guruswami, Madhu Sudan (1999) Improved decoding of Reed-Solomon and Algebraic-geometric codes. IEEE Transactions on Information Theory 45: 1757–1767
Venkatesan Guruswami & Madhu Sudan (2001). Extensions to the Johnson Bound. Manuscript. Available from http://people.csail.mit.edu/madhu/papers/johnson.ps.
Venkatesan Guruswami, Christopher Umans & Salil P. Vadhan (2009). Unbalanced expanders and randomness extractors from Parvaresh-Vardy codes. Journal of the ACM 56(4).
Ishay Haviv, Oded Regev (2012) Tensor-based Hardness of the Shortest Vector Problem to within Almost Polynomial Factors. Theory of Computing 8(1): 513–531
Ravi Kannan (1987) Minkowski’s Convex Body Theorem and Integer Programming. Mathematics of Operations Research 12(3): 415–440
Tali Kaufman, Shachar Lovett & Ely Porat (2010). Weight Distribution and List-Decoding Size of Reed- Muller Codes. In Innovations in Computer Science, 422–433.
Eyal Kushilevitz, Yishay Mansour (1993) Learning Decision Trees Using the Fourier Spectrum. SICOMP: SIAM Journal on Computing 22(6): 1331–1348
Florence J. MacWilliams & Neil J. A. Sloane (1981). The Theory of Error-Correcting Codes. Elsevier/North-Holland, Amsterdam.
Daniele Micciancio (2012) Inapproximability of the Shortest Vector Problem: Toward a Deterministic Reduction. Theory of Computing 8(1): 487–512
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.
Daniele Micciancio & Antonio Nicolosi (2008). Efficient Bounded Distance Decoder for Barnes-Wall Lattices. In IEEE International Symposium on Information Theory, 2484–2488.
Muller D. E. (1954) Application of Boolean algebra to switching circuit design and to error detection. IEEE Transactions on Computers 3: 6–12
Gabriele Nebe, Eric M. Rains & Neil J. A. Sloane (2001). The Invariants of the Clifford Groups. Designs, Codes and Cryptography 24(1), 99–122.
Farzad Parvaresh & Alexander Vardy (2005). Correcting Errors Beyond the Guruswami-Sudan Radius in Polynomial Time. In Symposium on Foundations of Computer Science, 285–294. Symposium on Foundations of Computer Science.
Ruud Pellikaan, Xin-Wen Wu (2004) List decoding of q-ary Reed-Muller codes. IEEE Transactions on Information Theory 50(4): 679–682
Xavier Pujol & Damien Stehlé (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–405.
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.
Irving Reed S. (1954) A class of multiple-error-correcting codes and the decoding scheme. IEEE Transactions on Information Theory 4: 38–49
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–3930.
Madhu Sudan (1997) Decoding of Reed Solomon Codes beyond the Error- Correction Bound. Journal of Complexity 13(1): 180–193
Madhu Sudan (2000) List decoding: algorithms and applications. SIGACT News 31(1): 16–27
Madhu Sudan (2001). Algorithmic Introduction to Coding Theory, Lecture Notes. Available from http://people.csail.mit.edu/madhu/FT01/.
Madhu Sudan, Luca Trevisan, Salil Vadhan P. (2001) Pseudorandom Generators without the XOR Lemma. Journal of Computer and System Sciences 62(2): 236–266
Amnon Ta-Shma & David Zuckerman (2001). Extractor codes. In ACM Symposium on Theory of Computing, 193–199.
Luca Trevisan (2001) Extractors and pseudorandom generators. Journal of the ACM 48(4): 860–879
John M. Wozencraft (1958). List Decoding. Quarterly Progress Report, Research Laboratory of Electronics, MIT 48, 90–95.
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Grigorescu, E., Peikert, C. List-Decoding Barnes–Wall Lattices. comput. complex. 26, 365–392 (2017). https://doi.org/10.1007/s00037-016-0151-x
Received:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00037-016-0151-x