Approximate CVP\(_p\) in time \(2^{0.802n}\)

DOI10.1016/j.jcss.2021.09.006zbMath1478.68449arXiv2005.04957OpenAlexW3202483697MaRDI QIDQ2051858

Moritz Venzin, Friedrich Eisenbrand

Publication date: 25 November 2021

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

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

zbMATH Keywords

sievinggeometric coveringalgorithmic geometry of numberslattice and integer programming

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Integer programming (90C10) Number-theoretic algorithms; complexity (11Y16) Approximation algorithms (68W25)

Related Items (1)

Approximate CVP in time \(2^{0.802 n}\) -- now in any norm!

Cites Work

• Unnamed Item
• Unnamed Item
• 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
• Lattice points in high-dimensional spheres
• The Shortest Vector in a Lattice is Hard to Approximate to within Some Constant
• 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
• 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
• Enumerative Lattice Algorithms in any Norm Via M-ellipsoid Coverings

This page was built for publication: Approximate CVP\(_p\) in time \(2^{0.802n}\)