On Approximating the Covering Radius and Finding Dense Lattice Subspaces

on YouTube ↗32m

" summary

Gives concrete claims: computes a near-optimal dense lattice subspace in single-exponential time (2^{O(n)}) and finds projection certificates that upper- and lower-bound the covering radius. Techniques are discrete Gaussian sampling on the dual lattice, an SDP relaxation for covering-radius lower bounds, and a use of reverse Minkowski. Guarantees: can approximate the densest sublattice to a O(log n) factor and produces a projection with bound about log^{2.5} n (compared to the l2 existential bound ~log^{3/2} n); some tightness depends on a Voronoi slicing conjecture.

AI-written summary · about

" chapters (27)

1. 0:00Intro
2. 0:15Outline
3. 0:46Integer Programming (IP)
4. 1:29Main Dichotomy
5. 4:05Duality Relation
6. 4:48Khinchine Flatness Theorem
7. 7:27Faster Algorithm for IP?
8. 11:13lz Covering Radius
9. 11:25Volumetric Lower Bounds
10. 13:56Known Bounds
11. 15:34Our Results
12. 17:32Rest of Talk
13. 17:54Notation
14. 18:36Canonical Polytope [Stuhler 76]
15. 20:36Stable Lattice [Stuhler 76]
16. 21:22Canonical Filtration Stuhler 76
17. 21:48KL for Stable Lattices
18. 22:54KL for all Lattices
19. 24:06Better Certificates for Chains
20. 25:43Finding Dense Subspaces
21. 26:23Densest Subspace Problem
22. 27:16Discrete Gaussian Distribution
23. 27:50Dual Lattice
24. 28:24High Level Algorithm
25. 29:00Reverse Minkowski Conjecture
26. 30:05Reverse Minkowski Theorem
27. 30:17Conclusions