On the Closest Vector Problem with a Distance Guarantee

Daniel Dadush, Oded Regev, Noah Stephens-Davidowitz

We present a substantially more efficient variant, both in terms of running time and size of preprocessing advice, of the algorithm by Liu, Lyubashevsky, and Micciancio for solving…