The polynomial-factor hardness conjecture for the Shortest Vector Problem
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.
Progress summary
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Sources & referencesView supporting material
Primary source
Min Jae Song, Ilias Zadik and Joan Bruna, “On the Cryptographic Hardness of Learning Single Periodic Neurons”, arXiv:2106.10744 (2021).
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.