3 problems

LLL approximation-barrier conjecture. The state-of-the-art LLL algorithm for $\mathrm{GapSVP}$ is only able to achieve an $2^{\Theta(n)}$-approximation, and any improvement on it w…

Quantum GapSVP hardness conjecture. There is no polynomial-time quantum algorithm that solves $\mathrm{GapSVP}$ to within polynomial factors.

Let $\mathrm{SVP}$ denote the Shortest Vector Problem on lattices, and let a polynomial-factor approximation mean an approximation within a factor bounded by a polynomial in the la…