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

We show a number of fine-grained hardness results for the Closest Vector Problem in the ℓp norm (CVPp), and its approximate and non-uniform variants. First, we show that CVPp cannot be solved in 2(1-varepsilon)n time for all p notin 2mathbbZ and varepsilon > 0, assuming the Strong Exponential Time Hypothesis (SETH). Second, we extend this by showing that there is no 2(1-varepsilon)n-time algorithm for approximating CVPp to within a constant factor γ for such p assuming a "gap" version of SETH, with an explicit relationship between γ, p, and the arity k = k(varepsilon) of the underlying hard CSP. Third, we show the same hardness result for (exact) CVPp with preprocessing (assuming non-uniform SETH). For exact "plain" CVPp, the same hardness result was shown in [Bennett, Golovnev, and Stephens-Davidowitz FOCS 2017] for all but finitely many p notin 2mathbbZ, where the set of exceptions depended on varepsilon 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 2mathbbZ is in some sense inherent. In particular, we show that no "natural" reduction can rule out even a 23n/4-time algorithm for CVP2 under SETH. For this, we prove that the possible sets of closest lattice vectors to a target in the ℓ2 norm have quite rigid structure, which essentially prevents them from being as expressive as 3-CNFs. We prove these results using techniques from many different fields, including complex analysis, functional analysis, additive combinatorics, and discrete Fourier analysis. E.g., along the way, we give a new (and tighter) proof of Szemer'edi's cube lemma for the boolean cube.