Fine-grained hardness of CVP(P)—Everything that we can prove (and nothing else)
Divesh Aggarwal, Huck Bennett, Alexander Golovnev, Noah Stephens-Davidowitz
Abstract
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–∊)n time for all p ∉ 2ℤ and ∊ > 0, assuming the Strong Exponential Time Hypothesis (SETH). Second, we extend this by showing that there is no 2(1–∊)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(∊) 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 ∉ 2ℤ, where the set of exceptions depended on ∊ 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 ∉ 2ℤ 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édi's cube lemma for the boolean cube. Please see the full version of this paper for the proofs of these results [1].