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

We show that the Closest Vector Problem in the l_p norm (CVP_p) cannot be solved in 2^{(1-\eps)n} time for all p \notin 2\Z and \eps > 0 (assuming SETH). In fact, we show that the same holds even for (1) the approximate version of the problem (assuming a gap version of SETH); and (2) CVP_p with preprocessing, in which we are allowed arbitrary advice about the lattice (assuming a non-uniform version of SETH). For “plain” CVP_p, the same hardness result was shown in [Bennett, Golovnev, and Stephens-Davidowitz FOCS 2017] for all but finitely many p \notin 2\Z, where the set of exceptions depended on \eps and was not explicit. For the approximate and preprocessing problems, only very weak bounds were known prior to this work.

We also show that the restriction to p \notin 2\Z is in some sense inherent. In particular, we show that no “natural” reduction can rule out even a 2^{3n/4}-time algorithm for \CVP_2 under SETH. For this, we prove that the possible sets of closest lattice vectors to a target in the \ell_2 norm have quite rigid structure, which essentially prevents them from being as expressive as 3-CNFs.

This talk is based on joint work with Divesh Aggarwal, Alexander Golovnev, and Noah Stephens-Davidowitz, available at https://arxiv.org/abs/1911.02440.