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