Complexity of Lattice Problems
summary
Defines precise reductions and runtimes: SVP reduces to CVP by doubling one basis coordinate, and CVP is NP‑hard via a subset‑sum basis construction that makes distance exactly √N when satisfiable. MAX‑2‑SAT maps to CVP to give constant‑factor hardness and Gap‑ETH fine‑grained lower bounds, while sparsification (pick inner product ≡0 mod Q) keeps about 1/Q of lattice points to eliminate short vectors. Hardness for SVP needs a locally dense gadget; recent constructions use Vladut’s lattices with exponential kissing number. Open: Euclidean fine‑grained and polynomial‑factor hardness.
AI-written summary · about
chapters (14)
- 0:00Introduction
- 0:55Shortest Vector Problem
- 2:48Simple Reduction
- 7:54Hardness of approximation
- 9:26Dream result
- 10:23Hardness of STP
- 21:48Canons embedding trick
- 24:22Ideal solution
- 25:39Sparse application
- 36:48Open problems
- 40:50Hardness approximation
- 45:46Looping questions
- 47:46Upper bounds
- 55:54Open problem
related talks
59mSome Recent Results Showing that Lattice Problems Are (sort of) Equivalent in All Norms
01h 06mHardness of the Shortest Vector Problem: A Simplified Proof and a Survey
01h 08mThe Mathematics of Lattices I
19mProvable Sieving Algorithms for SVP and CVP in the l_p norm
17mImproved Hardness of BDD and SVP Under Gap-(S)ETH
01h 40mHistorical Talk on Lattice-Based Cryptography
39mLattice Based Cryptography Primer
52mAn LLL Algorithm for Module Lattices