Solving the Closest Vector Problem in $2^n$ Time--- The Discrete Gaussian Strikes Again!

Divesh Aggarwal, Daniel Dadush, Noah Stephens-Davidowitz

We give a $2^{n+o(n)}$-time and space randomized algorithm for solving the exact Closest Vector Problem (CVP) on $n$-dimensional Euclidean lattices. This improves on the previous f…