On the (Classical and Quantum) Fine-Grained Complexity of Approximate CVP and Max-Cut

Abstract

We show a linear-size reduction from gap Max-2-Lin(2) (a generalization of the gap $\mathrm{Max}$-$\mathrm{Cut}$ problem) to $\gamma \text{-}{\mathrm{CVP}}_p$ for $\gamma =\mathrm{O}(1)$ and finite $p\ge 1$, as well as a no-go theorem against poly-sized non-adaptive quantum reductions from $k$-SAT to ${\mathrm{CVP}}_2$. This implies three headline results: (i) Faster algorithms for $\gamma \text{-}\mathrm{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 $\gamma \text{-}\mathrm{CVP}$ for $\gamma =\mathrm{O}(1)$ requires exponential time, improving upon the previous lower-bound for $\gamma <3$ by Bennett et al. [arxiv:1704.03928]. (ii) A new almost $2^{(1/2+\epsilon /4\varsigma +o(1))n}$-time classical algorithm and a new almost $2^{(1/3+\epsilon /6\varsigma +o(1))n}$-time quantum algorithm for $(1-\epsilon ,1-\varsigma )$-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_0\epsilon <\varsigma <c_1\epsilon$ for some constants $c_0,c_1$. (iii) If the Quantum Strong Exponential Time Hypothesis (QSETH) can be used to show a $2^{\delta n}$-time lower-bound for Max-Cut, Max-2-Lin(2), or ${\mathrm{CVP}}_2$ for any constant $\delta >0$, it must be via an adaptive quantum reduction unless $\mathrm{NP}\subseteq \mathrm{pr}\text{-}\mathrm{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.

arXiv comment38 pages, 4 figures