Approximate CVP_p in Time 2^{0.802 n}

DOI10.4230/LIPIcs.ESA.2020.43OpenAlexW3082158639MaRDI QIDQ5874513

Moritz Venzin, Friedrich Eisenbrand

Publication date: 7 February 2023

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

zbMATH Keywords

sievingapproximation algorithmcovering convex bodiesshortest and closest vector problem

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On weighted covering numbers and the Levi-Hadwiger conjecture
• Sampling methods for shortest vectors, closest vectors and successive minima
• A hierarchy of polynomial time lattice basis reduction algorithms
• Factoring polynomials with rational coefficients
• Intrinsic volumes and lattice points of crosspolytopes
• 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 some covering problems in geometry
• A deterministic single exponential time algorithm for most lattice problems based on voronoi cell computations
• Solving the Shortest Vector Problem in 2 ⁿ Time Using Discrete Gaussian Sampling
• A Geometric Analysis of the AWGN Channel With a <inline-formula> <tex-math notation="LaTeX">$(\sigma , \rho )$ </tex-math> </inline-formula>-Power Constraint
• Integer Programming with a Fixed Number of Variables
• Hardness of approximating the shortest vector problem in lattices
• Minkowski's Convex Body Theorem and Integer Programming
• A Greedy Heuristic for the Set-Covering Problem
• A random polynomial-time algorithm for approximating the volume of convex bodies
• A sieve algorithm for the shortest lattice vector problem
• (Gap/S)ETH hardness of SVP
• Just Take the Average! An Embarrassingly Simple $2^n$-Time Algorithm for SVP (and CVP)
• Convex and Discrete Geometry
• Covering cubes and the closest vector problem
• Convex Bodies The Brunn-MinkowskiTheory
• Enumerative Lattice Algorithms in any Norm Via M-ellipsoid Coverings

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