Fine-grained hardness of CVP(P) -- Everything that we can prove (and nothing else)

Divesh Aggarwal, Huck Bennett, Alexander Golovnev +1

We show a number of fine-grained hardness results for the Closest Vector Problem in the ${\ell }_p$ norm (${\mathrm{CVP}}_p$), and its approximate and non-uniform variants. First, we sh…