Approximating the closest vector problem using an approximate shortest vector oracle

DOI10.1007/978-3-642-22935-0_16zbMATH Open1343.68109OpenAlexW1491958686MaRDI QIDQ3088093FDOQ3088093

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

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

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (5)

• Reductions between short vector problems and simultaneous approximation
• Title not available (Why is that?)
• 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)