Abstract
We show a linear-size reduction from gap Max-2-Lin(2) (a generalization of the gap Max-Cut problem) to γ-CVP_p for γ = O(1) and finite p≥ 1, as well as a no-go theorem against poly-sized non-adaptive quantum reductions from k-SAT to CVP₂. This implies three headline results: (i) Faster algorithms for γ-CVP are also faster algorithms for Max-2-Lin(2) and Max-Cut. Depending on the approximation regime, even a 2^0.78n-time or 2^0.3n-time algorithm would improve upon the state-of-the-art algorithm such as Williams' 2004 algorithm [Theoretical Computer Science 2005] or Arora et al.'s 2010 algorithm [Journal of the ACM 2015]. This provides evidence that γ-CVP for γ=O(1) requires exponential time, improving upon the previous lower-bound for γ<3 by Bennett et al. [arxiv:1704.03928]. (ii) A new almost 2^(1/2+ε/4ς+o(1))n-time classical algorithm and a new almost 2^(1/3+ε/6ς+o(1))n-time quantum algorithm for (1-ε,1-ς)-gap Max-2-Lin(2). This algorithm is faster than the algorithm of Arora et al., as well as the algorithm of Williams, and the algorithm of Manurangsi and Trevisan [arxiv:1807.09898] when c₀ ε<ς<c₁ ε for some constants c₀, c₁. (iii) If the Quantum Strong Exponential Time Hypothesis (QSETH) can be used to show a 2^δ n-time lower-bound for Max-Cut, Max-2-Lin(2), or CVP₂ for any constant δ>0, it must be via an adaptive quantum reduction unless NP ⊆ pr-QSZK. This illuminates some difficulties in characterizing the hardness of approximate CSPs and shows that the post-quantum security of lattice-based cryptography likely cannot be supported by QSETH.