The reductions for the approximating covering radius problem

DOI10.1007/978-3-319-89500-0_5MaRDI QIDQ3297478zbMATH OpenOpenAlexFDO

Authors Wenwen Wang, Kewei Lv

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

covering bounded distance decoding problemcovering radius problemlatticepolynomial time reductions

Mathematics Subject Classification ID

Combinatorial codes (94B25) Decoding (94B35)

Recommendations

• On the Lattice Isomorphism Problem
• The complexity of the covering radius problem
• Search-to-decision reductions for lattice problems with approximation factors (slightly) greater than one
• Inapproximability Results for Computational Problems on Lattices
• Lattice problems and norm embeddings

Cites work

• 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
• Factoring polynomials with rational coefficients
• scientific article; zbMATH DE number 5764780 (Why is no real title available?)
• scientific article; zbMATH DE number 2120513 (Why is no real title available?)
• Lattice problems in NP ∩ coNP
• Limits on the hardness of lattice problems in \(\ell_{p}\) norms
• New bounds in some transference theorems in the geometry of numbers
• On Bounded Distance Decoding, Unique Shortest Vectors, and the Minimum Distance Problem
• On Lovász' lattice reduction and the nearest lattice point problem
• On the complexity of computing short linearly independent vectors and short bases in a lattice
• On the Lattice Isomorphism Problem
• On the limits of nonapproximability of lattice problems
• Sampling methods for shortest vectors, closest vectors and successive minima
• The complexity of the covering radius problem
• The remote set problem on lattices

Cited in

(4)

• Assigning weights to minimize the covering radius in the plane
• scientific article; zbMATH DE number 1057736 (Why is no real title available?)
• New Results on the Remote Set Problem and Its Applications in Complexity Study
• The complexity of the covering radius problem

This page was built for publication: The reductions for the approximating covering radius problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3297478)