Jeremy Ahrens Huang

We show a linear-size reduction from gap Max-2-Lin(2) (a generalization of the approximate Maximum Cut, or gap $\mathrm{Max}$-$\mathrm{Cut}$, problem) to $\gamma\text{-}\mathrm{CVP}_p$ for $\gamma = \mathrm{O}(1)$ and finite $p \geq 1$, as well as a no-go theorem against poly-sized non-adaptive quantum reductions from $k$-$\mathrm{SAT}$ to $\mathrm{CVP}_2$. This implies three headline results: (i) Faster algorithms for $\gamma\text{-}\mathrm{CVP}_p$ 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 [\textit{Theoretical Computer Science} 2005] or Arora, Barak, and Steurer's 2010 algorithm [$\textit{Journal of the ACM}$ 2015]. This provides evidence that $\gamma\text{-}\mathrm{CVP}_p$ for $\gamma = o(\sqrt{\log n}^\frac{1}{p})$ requires $2^{\delta n}$-time for some specific constant $\delta > 0$, improving upon the previous exponential lower-bound for $\gamma\text{-}\mathrm{CVP}_2$ with $\gamma < 3$ by Bennett, Golovnev, and Stephens-Davidowitz [$\textit{FOCS}$ 2017]. (ii) A new almost $2^{(1/2 + \varepsilon/4\varsigma + o(1)) n}$-time classical algorithm and a new almost $2^{(1/3 + \varepsilon/6\varsigma + o(1)) n}$-time quantum algorithm for $(1-\varepsilon, 1-\varsigma)$-gap Max-Cut. This algorithm is faster than the algorithm of Arora, Barak and Steuer [$\textit{Journal of the ACM}$ 2015], as well as the algorithm of Williams [$\textit{Theoretical Computer Science}$ 2004], % and others and the algorithm of Manurangsi and Trevisan [\textit{APPROX/RANDOM} 2018] when $c_0 \varepsilon < \varsigma < c_1 \varepsilon$ 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 $\mathrm{Max}$-$\mathrm{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 constraint satisfaction problems and shows that the post-quantum security of lattice-based cryptography likely cannot be supported by QSETH. This result builds off of and strengthens the no-go results of Aggarwal and Kumar [$\textit{FOCS}$ 2023], who showed that the classical security of lattice-based cryptography likely cannot be supported by the classical Strong Exponential Time Hypothesis (SETH).