The polynomial-factor hardness conjecture for the Shortest Vector Problem
Let 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 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
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.