Approximate CVP_p in Time 2^{0.802 n}

DOI10.4230/LIPICS.ESA.2020.43MaRDI QIDQ5874513zbMATH OpenOpenAlexFDO

Authors Friedrich Eisenbrand, Moritz Venzin

Publication date 7 February 2023

Full work available at URL https://doi.org/10.4230/LIPIcs.ESA.2020.43

zbMATH Keywords

approximation algorithmcovering convex bodiesshortest and closest vector problemsieving

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx)

Cites work

• (Gap/S)ETH hardness of SVP
• A deterministic single exponential time algorithm for most lattice problems based on Voronoi cell computations
• A Geometric Analysis of the AWGN Channel With a <inline-formula> <tex-math notation="LaTeX">$(\sigma , \rho )$ </tex-math> </inline-formula>-Power Constraint
• 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
• Convex Bodies The Brunn-MinkowskiTheory
• 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 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?)
• 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)
• Minkowski's Convex Body Theorem and Integer Programming
• On some covering problems in geometry
• 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

This page was built for publication: Approximate CVP_p in Time 2^{0.802 n}

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