Approximating the Closest Vector Problem Using an Approximate Shortest Vector Oracle
From MaRDI portal
Publication:3088093
DOI10.1007/978-3-642-22935-0_16zbMath1343.68109OpenAlexW1491958686MaRDI QIDQ3088093
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
Analysis of algorithms and problem complexity (68Q25) Lattices and convex bodies (number-theoretic aspects) (11H06)
Related Items
Cites Work
- A hierarchy of polynomial time lattice basis reduction algorithms
- Factoring polynomials with rational coefficients
- New bounds in some transference theorems in the geometry of numbers
- Approximating shortest lattice vectors is not harder than approximating closest lattice vectors
- Approximating CVP to within almost-polynomial factors is NP-hard
- The Shortest Vector in a Lattice is Hard to Approximate to within Some Constant
- 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
- On Bounded Distance Decoding, Unique Shortest Vectors, and the Minimum Distance Problem
- Hardness of approximating the shortest vector problem in lattices
- Minkowski's Convex Body Theorem and Integer Programming
- Public-key cryptosystems from the worst-case shortest vector problem
- A sieve algorithm for the shortest lattice vector problem
- New lattice-based cryptographic constructions
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
This page was built for publication: Approximating the Closest Vector Problem Using an Approximate Shortest Vector Oracle