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 ${\hat{I}}^3\text{-}{\mathrm{CVP}}_p$ for ${\hat{I}}^3=\mathrm{O}(1)$ and…