Approximate CVP_p in time 2⁰.802n
From MaRDI portal
Publication:2051858
Abstract: We show that a constant factor approximation of the shortest and closest lattice vector problem w.r.t. any -norm can be computed in time . This matches the currently fastest constant factor approximation algorithm for the shortest vector problem w.r.t. . To obtain our result, we combine the latter algorithm w.r.t. with geometric insights related to coverings.
Recommendations
- Approximate CVP in time \(2^{0.802 n}\) -- now in any norm!
- scientific article; zbMATH DE number 6607548
- Lattice sparsification and the approximate closest vector problem
- Approximating shortest lattice vectors is not harder than approximating closest lattice vectors
- Hardness of approximating the shortest vector problem in lattices
Cites work
- (Gap/S)ETH hardness of SVP
- A deterministic single exponential time algorithm for most lattice problems based on Voronoi cell computations
- A Greedy Heuristic for the Set-Covering Problem
- A hierarchy of polynomial time lattice basis reduction algorithms
- A random polynomial-time algorithm for approximating the volume of convex bodies
- 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
- Convex and Discrete Geometry
- Covering cubes and the closest vector problem
- Enumerative Lattice Algorithms in any Norm Via M-ellipsoid Coverings
- Factoring polynomials with rational coefficients
- Faster exponential time algorithms for the shortest vector problem
- Hardness of approximating the shortest vector problem in lattices
- scientific article; zbMATH DE number 5485482 (Why is no real title available?)
- scientific article; zbMATH DE number 3633251 (Why is no real title available?)
- scientific article; zbMATH DE number 1330032 (Why is no real title available?)
- scientific article; zbMATH DE number 1182906 (Why is no real title available?)
- scientific article; zbMATH DE number 1775383 (Why is no real title available?)
- scientific article; zbMATH DE number 6607548 (Why is no real title available?)
- Improved algorithms for the shortest vector problem and the closest vector problem in the infinity norm
- Integer Programming with a Fixed Number of Variables
- Intrinsic volumes and lattice points of crosspolytopes
- Just take the average! An embarrassingly simple \(2^n\)-time algorithm for SVP (and CVP)
- Lattice points in high-dimensional spheres
- Minkowski's Convex Body Theorem and Integer Programming
- On weighted covering numbers and the Levi-Hadwiger conjecture
- Sampling methods for shortest vectors, closest vectors and successive minima
- Solving the shortest vector problem in 2ⁿ time using discrete Gaussian sampling (extended abstract)
- The shortest vector in a lattice is hard to approximate to within some constant
Cited in
(15)- Approximating shortest lattice vectors is not harder than approximating closest lattice vectors
- Covering convex bodies and the closest vector problem
- Approximate CVP in time \(2^{0.802 n}\) -- now in any norm!
- Closest periodic vectors in \(L_p\) spaces
- Closest periodic vectors in L_p spaces
- On Polynomial-Factor Approximations to the Shortest Lattice Vector Length
- Covering cubes and the closest vector problem
- Lattice sparsification and the approximate closest vector problem
- The nearest-colattice algorithm: time-approximation tradeoff for approx-CVP
- Improvements in the analysis of Kannan's CVP algorithm
- Economical convex coverings and applications
- Delaunay triangulations in the Hilbert metric
- Improved provable reduction of NTRU and hypercubic lattices
- Farthest-point Voronoi diagrams in the Hilbert metric
- A polynomial time algorithm for GapCVPP in \(l_1\) norm
This page was built for publication: Approximate CVP\(_p\) in time \(2^{0.802n}\)
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2051858)
