The complexity of the covering radius problem

DOI10.1007/s00037-005-0193-yzbMath1085.68063OpenAlexW2000333212MaRDI QIDQ814418

Daniele Micciancio, Venkatesan Guruswami, Oded Regev

Publication date: 7 February 2006

Published in: Computational Complexity (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00037-005-0193-y

zbMATH Keywords

covering radiuslinear codeslatticesapproximation algorithmsinteractive proofshardness of approximationcomplexity classespolynomial time hierarchy

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Linear codes (general theory) (94B05) Lattices and convex bodies (number-theoretic aspects) (11H06) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Lattice packing and covering (number-theoretic aspects) (11H31) Applications of the theory of convex sets and geometry of numbers (covering radius, etc.) to coding theory (94B75)

Related Items (14)

New transference theorems on lattices possessing \(n^\varepsilon\)-unique shortest vectors ⋮ Covering Radius of Matrix Codes Endowed with the Rank Metric ⋮ On the number of lattice points in a small sphere and a recursive lattice decoding algorithm ⋮ Some questions related to the reverse Minkowski theorem ⋮ The Reductions for the Approximating Covering Radius Problem ⋮ Linear discrepancy is \(\Pi_2\)-hard to approximate ⋮ Algorithms for the Shortest and Closest Lattice Vector Problems ⋮ Improved Zero-Knowledge Proofs of Knowledge for the ISIS Problem, and Applications ⋮ Complexity and algorithms for computing Voronoi cells of lattices ⋮ A note on the distribution of the distance from a lattice ⋮ Towards uniform online spherical tessellations ⋮ The Geometry of Lattice Cryptography ⋮ The Restricted Isometry Property of Subsampled Fourier Matrices ⋮ The remote set problem on lattices

This page was built for publication: The complexity of the covering radius problem