Approximating the closest vector problem using an approximate shortest vector oracle

DOI10.1007/978-3-642-22935-0_16MaRDI QIDQ3088093zbMATH OpenOpenAlexFDO

Authors Thomas Holenstein, Chandan K. Dubey

Publication date 17 August 2011

Published in Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-642-22935-0_16

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Lattices and convex bodies (number-theoretic aspects) (11H06)

Recommendations

• Approximating shortest lattice vectors is not harder than approximating closest lattice vectors
• The shortest vector in a lattice is hard to approximate to within some constant
• Reductions between short vector problems and simultaneous approximation
• Note on shortest and nearest lattice vectors
• Hardness of approximating the shortest vector problem in lattices

Cites work

• scientific article; zbMATH DE number 5485482 (Why is no real title available?)
• scientific article; zbMATH DE number 5764780 (Why is no real title available?)
• scientific article; zbMATH DE number 1256724 (Why is no real title available?)
• scientific article; zbMATH DE number 1775383 (Why is no real title available?)
• scientific article; zbMATH DE number 2120513 (Why is no real title available?)
• A deterministic single exponential time algorithm for most lattice problems based on Voronoi cell computations
• A hierarchy of polynomial time lattice basis reduction algorithms
• A sieve algorithm for the shortest lattice vector problem
• Approximating CVP to within almost-polynomial factors is NP-hard
• Approximating shortest lattice vectors is not harder than approximating closest lattice vectors
• Factoring polynomials with rational coefficients
• Hardness of approximating the shortest vector problem in lattices
• Minkowski's Convex Body Theorem and Integer Programming
• New bounds in some transference theorems in the geometry of numbers
• New lattice-based cryptographic constructions
• On Bounded Distance Decoding, Unique Shortest Vectors, and the Minimum Distance Problem
• On the complexity of computing short linearly independent vectors and short bases in a lattice
• Public-key cryptosystems from the worst-case shortest vector problem
• The shortest vector in a lattice is hard to approximate to within some constant

Cited in

(5)

• Reductions between short vector problems and simultaneous approximation
• scientific article; zbMATH DE number 6607548 (Why is no real title available?)
• The reductions for the approximating covering radius problem
• Search-to-decision reductions for lattice problems with approximation factors (slightly) greater than one
• Approximating shortest lattice vectors is not harder than approximating closest lattice vectors

This page was built for publication: Approximating the closest vector problem using an approximate shortest vector oracle

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