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

Jeremy Ahrens Huang, Young Kun Ko, Chunhao Wang

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 fi…