No Karp reduction from NP to GapSVP for γ ≥ √(n/log n) unless coNP ⊆ AM

Unconditional · GG00, BHZ87

Statement

For $\gamma =c\sqrt{n/\log n}$, ${\mathrm{GapSVP}}_{\gamma }$ (GapSVP) and ${\mathrm{GapCVP}}_{\gamma }$ lie in $\mathbf{NP}\cap \mathbf{coAM}$ (GapSVP ∈ coAM) — GG00. A Karp reduction from an $\mathbf{NP}$-complete problem to them would therefore give $\mathbf{coNP}\subseteq \mathbf{AM}$, which collapses the polynomial hierarchy to its second level — BHZ87.