Hardness of the Shortest Vector Problem: A Simplified Proof and a Survey
summary
Claims a simpler randomized NP‑hardness reduction for GAP‑SVP that builds Reed–Solomon parity‑check lattices (prime Q, K ≈ Q^ε), shows L1 minimum distance ≈ 2K and determinant Q^K, and obtains ≥ Q^{(2α−1)K} short coset vectors for α>1/2. Main tool is stacking that gadget under CVP via Kan and using a locally dense lattice to force large λ1; randomness enters by sampling a coset center S. Derandomization routes via Weil bounds and discrete Fourier ideas remain inconclusive.
AI-written summary · about
chapters (17)
- 0:00Workshop introduction
- 2:22Lattice problem fundamentals
- 5:39Complexity of lattice problems
- 7:25Hard regime and code comparisons
- 11:59Deterministic vs randomized
- 14:43Quantum and classical reduction
- 18:21New hardness proof overview
- 20:48Reducing CVP to SVP
- 23:11Analysis of the reduction
- 28:37Locally dense lattices
- 31:09Randomness in constructions
- 36:40Constructions and code theory
- 39:31Reed-Solomon based lattices
- 43:58Parameters of the lattice
- 50:55De-randomization strategies
- 53:50Future directions and conclusion
- 57:38Q&A and discussion
related talks
01h 03mComplexity of Lattice Problems
01h 08mThe Mathematics of Lattices I
01h 13mAlgorithms for Lattice Problems
01h 36mAlgorithms for Algebraic Lattices: Classical and Quantum
33mSolving SVP and CVP in 2^n time with Discrete Gaussian Sampling – Noah Stephens-Davidowitz
17mImproved Hardness of BDD and SVP Under Gap-(S)ETH
19mProvable Sieving Algorithms for SVP and CVP in the l_p norm
37mSolving SVP and CVP in 2^n time with Discrete Gaussian Sampling – Daniel Dadush