Some Recent Results Showing that Lattice Problems Are (sort of) Equivalent in All Norms
summary
Shows that for large constant approximation factors lattice problems in any Lp norm run in essentially the same time as in L2, giving a 2^{0.8n} algorithm for CVP/SVP in arbitrary norms by: transform the convex body into an L2-like position, sample targets from K+ball, use an L2 CVP oracle to produce exponentially many short L2 vectors, then pairwise differences yield an O(1)-approximate Lp solution; reductions are dimension-preserving reductions running in 2^{εn} and rely on M‑ellipsoid style coverings.
AI-written summary · about
chapters (11)
- 0:00Introduction to lattice norms
- 1:09Fundamentals of lattices
- 4:26Approximation and CVP
- 7:30L2 and Infinity norms
- 13:03Historical context and goals
- 19:12Breakthrough algorithms
- 23:20Complexity and wiggles
- 29:40The algorithmic mechanism
- 37:05Reductions and sparsification
- 43:20Transformation and geometry
- 51:43Summary and future outlook
related talks
01h 03mComplexity of Lattice Problems
19mProvable Sieving Algorithms for SVP and CVP in the l_p norm
01h 13mAlgorithms for Lattice Problems
33mSolving SVP and CVP in 2^n time with Discrete Gaussian Sampling – Noah Stephens-Davidowitz
01h 08mThe Mathematics of Lattices I
37mSolving SVP and CVP in 2^n time with Discrete Gaussian Sampling – Daniel Dadush
01h 36mAlgorithms for Algebraic Lattices: Classical and Quantum
01h 00mA Reverse Minkowski Theorem