The Reductions for the Approximating Covering Radius Problem

DOI10.1007/978-3-319-89500-0_5zbMath1452.94129OpenAlexW2797616583MaRDI QIDQ3297478

Kewei Lv, Wenwen Wang

Publication date: 20 July 2020

Published in: Information and Communications Security (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-319-89500-0_5

zbMATH Keywords

latticecovering radius problempolynomial time reductionscovering bounded distance decoding problem

Mathematics Subject Classification ID

Combinatorial codes (94B25) Decoding (94B35)

Cites Work

• Unnamed Item
• Unnamed Item
• The complexity of the covering radius problem
• Limits on the hardness of lattice problems in \(\ell_{p}\) norms
• Sampling methods for shortest vectors, closest vectors and successive minima
• On Lovász' lattice reduction and the nearest lattice point problem
• Factoring polynomials with rational coefficients
• New bounds in some transference theorems in the geometry of numbers
• On the limits of nonapproximability of lattice problems
• The remote set problem on lattices
• On the complexity of computing short linearly independent vectors and short bases in a lattice
• A Deterministic Single Exponential Time Algorithm for Most Lattice Problems Based on Voronoi Cell Computations
• Approximating the Closest Vector Problem Using an Approximate Shortest Vector Oracle
• On Bounded Distance Decoding, Unique Shortest Vectors, and the Minimum Distance Problem
• Lattice problems in NP ∩ coNP
• On the Lattice Isomorphism Problem

This page was built for publication: The Reductions for the Approximating Covering Radius Problem