A Reverse Minkowski Theorem

on YouTube ↗01h 00m

" summary

Proves a precise reverse Minkowski: local → sublattice density statement: if every sublattice has det ≥1 then any ball has at most 2^{O(n)} Gaussian mass (and point count), with the worst case morally Z^n and a remaining √log n loss in parameters. Proof converts point counts to the Gaussian mass and Voronoi cell, moves to the compact space of stable lattices, uses projection/induction and convex-geometry results (L-position/B-conjecture inputs). Yields algorithmic and mixing-time consequences (and a 2^{n/2}-time Hermite SVP corollary).

AI-written summary · about

" chapters (15)

1. 0:00A Reverse Minkowski Theorem
2. 4:28Counting Lattice Points: Pop Quiz!
3. 5:24Determinant of a Lattice
4. 9:02Minkowski's Theorem
5. 23:06Applications: Algorithms for Hermite SVP
6. 24:03Spoiler
7. 24:59Gaussian Mass
8. 30:09Space of (Stable) Lattices
9. 33:47Ct lies on the boundary
10. 36:57Dream Proof Fails
11. 41:38Slightly Less Dreamy Proof
12. 42:34Our Actual Proof
13. 48:29The Actual Theorem
14. 50:12Summary
15. 51:24Open Questions

" related talks

• 01h 42mMathematics of LatticesDaniele Micciancio · Lattices: Algorithms, Complexity, and Cryptography Boot Camp 2020
• 59mSome Recent Results Showing that Lattice Problems Are (sort of) Equivalent in All NormsNoah Stephens-Davidowitz · Quantum and Lattices Joint Reunion Workshop
• 01h 08mThe Mathematics of Lattices IVinod Vaikuntanathan · Cryptography Boot Camp 2015
• 01h 36mAlgorithms for Algebraic Lattices: Classical and QuantumLéo Ducas · Lattices: Algorithms, Complexity, and Cryptography Boot Camp 2020
• 01h 13mAlgorithms for Lattice ProblemsNoah Stephens-Davidowitz · Lattices: Algorithms, Complexity, and Cryptography Boot Camp 2020
• 01h 03mComplexity of Lattice ProblemsNoah Stephens-Davidowitz · Lattices: Algorithms, Complexity, and Cryptography Boot Camp 2020
• 01h 04mThe Mathematics of Lattices IIVinod Vaikuntanathan · Cryptography Boot Camp 2015
• 57mAlgorithms for Lattice Problems, in PracticeElena Kirshanova, Pierre-Alain Fouque · Lattices: Algorithms, Complexity, and Cryptography Boot Camp 2020