Provable Sieving Algorithms for SVP and CVP in the l_p norm
summary
Presents provable sieving methods for SVP and CVP in lp norms that replace AKS-style ball covers with partitions of the LP ball into hypercubes, allowing center assignment by simple coordinate bucketing. The linear sieve achieves time roughly 2^{0.751 n} for SVP (claimed faster than prior AKS-type bounds) while its space usage increases compared to quadratic sieves. A hybrid linear+quadratic procedure trades extra memory for further time improvement and yields comparable approximate-CVP routines.
AI-written summary · about
chapters (9)
- 0:00Intro
- 1:17Fundamental Parallelepiped
- 2:20Shortest Vector Problem SVP
- 4:01Applications of SVP and CVP
- 4:25Prior Works: Sieving algorithms for SVP and CVP
- 6:20Hardness results for SVP and CVP
- 10:04Complexity of AKS sieve
- 11:56Number of partitions (hypercubes)
- 13:25Comparison of space and time complexity
related talks
01h 13mAlgorithms for Lattice Problems
59mSome Recent Results Showing that Lattice Problems Are (sort of) Equivalent in All Norms
01h 03mComplexity of Lattice Problems
37mSolving SVP and CVP in 2^n time with Discrete Gaussian Sampling – Daniel Dadush
33mSolving SVP and CVP in 2^n time with Discrete Gaussian Sampling – Noah Stephens-Davidowitz
01h 06mHardness of the Shortest Vector Problem: A Simplified Proof and a Survey
01h 36mAlgorithms for Algebraic Lattices: Classical and Quantum
01h 08mThe Mathematics of Lattices I