Approximate CVP_p in Time 2^{0.802 n}

DOI10.4230/LIPICS.ESA.2020.43OpenAlexW3082158639MaRDI QIDQ5874513FDOQ5874513

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 algorithmsievingcovering convex bodiesshortest and closest vector problem

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx)

Cites Work

• A hierarchy of polynomial time lattice basis reduction algorithms
• A deterministic single exponential time algorithm for most lattice problems based on Voronoi cell computations
• A sieve algorithm for the shortest lattice vector problem
• Convex and Discrete Geometry
• A Greedy Heuristic for the Set-Covering Problem
• Convex Bodies The Brunn-MinkowskiTheory
• Factoring polynomials with rational coefficients
• Integer Programming with a Fixed Number of Variables
• Minkowski's Convex Body Theorem and Integer Programming
• A random polynomial-time algorithm for approximating the volume of convex bodies
• Title not available (Why is that?)
• Title not available (Why is that?)
• Approximating CVP to within almost-polynomial factors is NP-hard
• Title not available (Why is that?)
• Enumerative Lattice Algorithms in any Norm Via M-ellipsoid Coverings
• Intrinsic volumes and lattice points of crosspolytopes
• The shortest vector in a lattice is hard to approximate to within some constant
• Title not available (Why is that?)
• Sampling methods for shortest vectors, closest vectors and successive minima
• Approximating shortest lattice vectors is not harder than approximating closest lattice vectors
• Covering cubes and the closest vector problem
• On weighted covering numbers and the Levi-Hadwiger conjecture
• On some covering problems in geometry
• Title not available (Why is that?)
• Solving the shortest vector problem in \(2^n\) time using discrete Gaussian sampling (extended abstract)
• Hardness of approximating the shortest vector problem in lattices
• Faster exponential time algorithms for the shortest vector problem
• (Gap/S)ETH hardness of SVP
• Just take the average! An embarrassingly simple \(2^n\)-time algorithm for SVP (and CVP)
• A Geometric Analysis of the AWGN Channel With a <inline-formula> <tex-math notation="LaTeX">$(\sigma , \rho )$ </tex-math> </inline-formula>-Power Constraint

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)