How to Round Spiky Balls into Submission; And Faster Algorithms For The Closest Vector ProblemResearch Paper
The Closest Vector Problem asks for the point of a lattice nearest to a given target. It is a central problem of the algorithmic geometry of numbers: integer programming in fixed dimension, lattice-based cryptanalysis and many reductions between lattice problems pass through it. Its complexity depends on the norm. In the Euclidean norm, exact CVP is solved…