2019/11/06 by Divesh Aggarwal, Huck Bennett, Aggarwal, Divesh +5
Computer Science · #Complexity and Algorithms in Graphs #Computational Complexity (cs.CC) #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Machine Learning and Algorithms #Optimization and Search Problems
paper · doi:10.48550/arxiv.1911.02440
openalex publication_date 2019/11/06 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/29
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.