The polynomial-factor hardness conjecture for the Shortest Vector Problem

About 5 years old · traced to

Let SVP\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 lattice dimension. Polynomial-factor SVP hardness conjecture. There is no polynomial-time quantum algorithm that approximates SVP\mathrm{SVP} to within polynomial factors. This is the widely believed worst-case hardness assumption underlying the cryptographic evidence for the computational hardness of continuous learning with errors.

References

Primary source

Min Jae Song, Ilias Zadik and Joan Bruna, “On the Cryptographic Hardness of Learning Single Periodic Neurons”, arXiv:2106.10744 (2021).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.