List-decoding Barnes-Wall lattices
From MaRDI portal
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 structure of linear codes and point lattices in 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 L in R^N, given a target vector r in R^N and a distance parameter d, output the set of all lattice points w in 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 (up to polynomials) 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) Building on the unique decoding algorithm of Micciancio and Nicolosi (ISIT '08), we give a list-decoding algorithm that runs in time polynomial in the lattice dimension and worst-case list size, for any error radius. Moreover, our algorithm is highly parallelizable, and with sufficiently many processors can run in parallel time only poly-logarithmic in the lattice dimension. In particular, our results imply a polynomial-time list-decoding algorithm for any error radius bounded away from the minimum distance, thus beating a typical barrier for error-correcting codes posed by the Johnson radius.
Recommendations
- Lattice (List) Decoding Near Minkowski’s Inequality
- scientific article; zbMATH DE number 1759459
- Combinatorial bounds for list decoding
- Algorithmic Results in List Decoding
- List-decoding multiplicity codes
- List-Decoding Algorithms for Lifted Codes
- A new encoding approach: Barnes-Wall product lattice
- List-decoding homomorphism codes with arbitrary codomains
- List decoding of convolutional codes
- List decoding codes on Garcia-Stichtenoth tower using Gröbner basis
Cites work
- scientific article; zbMATH DE number 5485538 (Why is no real title available?)
- scientific article; zbMATH DE number 5485539 (Why is no real title available?)
- scientific article; zbMATH DE number 3957109 (Why is no real title available?)
- scientific article; zbMATH DE number 1759459 (Why is no real title available?)
- scientific article; zbMATH DE number 1852134 (Why is no real title available?)
- scientific article; zbMATH DE number 2120513 (Why is no real title available?)
- Algorithmic Results in List Decoding
- An improved list decoding algorithm for the second order Reed-Muller codes and its applications
- Augmented Product Codes and Lattices: Reed–Muller Codes and Barnes–Wall Lattices
- Bridging Shannon and Hamming: list error-correction with optimal rate
- Coset codes. II. Binary lattices and related codes
- Decoding of Reed Solomon codes beyond the error-correction bound
- Explicit capacity-achieving list-decodable codes
- Extractor codes
- Extractors and pseudorandom generators
- Generalized minimum distance decoding in Euclidean space: performance analysis
- Generalized minimum-distance decoding of Euclidean-space codes and lattices
- Hardness of approximating the minimum distance of a linear code
- Ideal forms of Coppersmith's theorem and Guruswami-Sudan list decoding
- Improved decoding of Reed-Solomon and algebraic-geometry codes
- Inapproximability of the shortest vector problem: toward a deterministic reduction
- Learning Decision Trees Using the Fourier Spectrum
- List Decoding of Biorthogonal Codes and the Hadamard Transform With Linear Complexity
- List Decoding of<tex>$q$</tex>-ary Reed–Muller Codes
- List decoding of error-correcting codes. Winning thesis of the 2002 ACM Doctoral Dissertation Competition
- List-decoding Barnes-Wall lattices
- Minkowski's Convex Body Theorem and Integer Programming
- Near-optimal sparse fourier representations via sampling
- Pseudorandom generators without the XOR lemma
- Recursive error correction for general Reed--Muller codes
- Rigorous and Efficient Short Lattice Vectors Enumeration
- Soft-decision decoding of Reed-Muller codes: recursive lists
- Soft-decision majority decoding of Reed-Muller codes
- Some extreme forms defined in terms of Abelian groups
- Tensor-based hardness of the shortest vector problem to within almost polynomial factors
- The invariants of the Clifford groups
- Trellis complexity and minimal trellis diagrams of lattices
- Unbalanced expanders and randomness extractors from Parvaresh-Vardy codes
- Weight Distribution and List-Decoding Size of Reed–Muller Codes
Cited in
(5)- List-decoding Barnes-Wall lattices
- Polynomial time bounded distance decoding near Minkowski's bound in discrete logarithm lattices
- Ideal forms of Coppersmith's theorem and Guruswami-Sudan list decoding
- A new complex reflection group in \(PU(9,1)\) and the Barnes-Wall lattice
- Construction-D lattice from Garcia–Stichtenoth tower code
This page was built for publication: List-decoding Barnes-Wall lattices
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2410678)
