Covering convex bodies and the closest vector problem
DOI10.1007/s00454-022-00392-xzbMath1492.90090arXiv1908.08384OpenAlexW2969970306MaRDI QIDQ2136842
Publication date: 16 May 2022
Published in: Discrete \& Computational Geometry (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1908.08384
approximationmodulus of smoothnessclosest vector problemconvex body in \(d\)-dimensional spacelattice sparsification
Analysis of algorithms and problem complexity (68Q25) Lattices and convex bodies in (n) dimensions (aspects of discrete geometry) (52C07) Integer programming (90C10) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Approximation algorithms (68W25)
Related Items (1)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Sampling methods for shortest vectors, closest vectors and successive minima
- Geometric algorithms and combinatorial optimization
- Entropy and asymptotic geometry of non-symmetric convex bodies
- On the combinatorial complexity of approximating polytopes
- Approximating CVP to within almost-polynomial factors is NP-hard
- A deterministic single exponential time algorithm for most lattice problems based on voronoi cell computations
- A O(1/ε 2) n -Time Sieving Algorithm for Approximate Integer Programming
- 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
- Economical Delone Sets for Approximating Convex Bodies
- A sieve algorithm for the shortest lattice vector problem
- Just Take the Average! An Embarrassingly Simple $2^n$-Time Algorithm for SVP (and CVP)
- Covering cubes and the closest vector problem
- Enumerative Lattice Algorithms in any Norm Via M-ellipsoid Coverings
- On compact representations of Voronoi cells of lattices
- The geometry of Minkowski spaces -- a survey. I
This page was built for publication: Covering convex bodies and the closest vector problem
