Approximate CVP in time 2⁰.802 n -- now in any norm!

DOI10.1007/978-3-031-06901-7_33MaRDI QIDQ2164729zbMATH OpenOpenAlexFDO

Authors Thomas Rothvoß, Moritz Venzin

Publication date 16 August 2022

Full work available at URL https://arxiv.org/abs/2110.02387

zbMATH Keywords

integer programminglattice algorithmssieving

Mathematics Subject Classification ID

Integer programming (90C10)

Abstract: We show that a constant factor approximation of the shortest and closest lattice vector problem in any norm can be computed in time $2^{0.802,n}$. This contrasts the corresponding $2^n$ time, (gap)-SETH based lower bounds for these problems that even apply for small constant approximation. For both problems, $mathrmSVP$ and $mathrmCVP$, we reduce to the case of the Euclidean norm. A key technical ingredient in that reduction is a twist of Milman's construction of an $M$-ellipsoid which approximates any symmetric convex body $K$ with an ellipsoid $mathcalE$ so that $2^{varepsilonn}$ translates of a constant scaling of $mathcalE$ can cover $K$ and vice versa.

Recommendations

• Approximate CVP\(_p\) in time \(2^{0.802n}\)
• Covering convex bodies and the closest vector problem
• scientific article; zbMATH DE number 6607548
• Lattice sparsification and the approximate closest vector problem
• Covering cubes and the closest vector problem

Cites work

• (Gap/S)ETH hardness of SVP
• A \(O(1/\epsilon ^{2})^{n }\)-time sieving algorithm for approximate integer programming
• 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
• Approximate CVP\(_p\) in time \(2^{0.802n}\)
• Approximating CVP to within almost-polynomial factors is NP-hard
• Approximating shortest lattice vectors is not harder than approximating closest lattice vectors
• Covering convex bodies and the closest vector problem
• Covering cubes and the closest vector problem
• Discrete Gaussian sampling reduces to CVP and SVP
• Efficient checking of polynomials and proofs and the hardness of approximation problems
• Enumerative Lattice Algorithms in any Norm Via M-ellipsoid Coverings
• Factoring polynomials with rational coefficients
• Faster exponential time algorithms for the shortest vector problem
• Fully homomorphic encryption using ideal lattices
• Hardness of approximating the shortest vector problem in lattices
• scientific article; zbMATH DE number 4213909 (Why is no real title available?)
• 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 1256724 (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?)
• scientific article; zbMATH DE number 3052220 (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
• Just take the average! An embarrassingly simple \(2^n\)-time algorithm for SVP (and CVP)
• Lattice problems and norm embeddings
• Lattice problems in NP ∩ coNP
• Limits on the hardness of lattice problems in \(\ell_{p}\) norms
• Minkowski's Convex Body Theorem and Integer Programming
• On lattices, learning with errors, random linear codes, and cryptography
• On Lovász' lattice reduction and the nearest lattice point problem
• On some covering problems in geometry
• On the limits of nonapproximability of lattice problems
• 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

(10)

• Approximate CVP\(_p\) in time \(2^{0.802n}\)
• Covering convex bodies and the closest vector problem
• Lattice problems and norm embeddings
• Covering cubes and the closest vector problem
• Deterministic construction of an approximate M-ellipsoid and its applications to derandomizing lattice algorithms
• The nearest-colattice algorithm: time-approximation tradeoff for approx-CVP
• Verification of NP-Hardness Reduction Functions for Exact Lattice Problems
• Economical convex coverings and applications
• Delaunay triangulations in the Hilbert metric
• Farthest-point Voronoi diagrams in the Hilbert metric

This page was built for publication: Approximate CVP in time \(2^{0.802 n}\) -- now in any norm!

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