On Approximating the Covering Radius and Finding Dense Lattice Subspaces

on YouTube ↗01h 00m

" summary

Links covering-radius approximation to integer programming by reducing to lattice enumeration using M-ellipsoids and Voronoi connectivity, gives single-exponential enumeration when the worst-shift lattice count is bounded; introduces the canonical filtration (lower convex hull of log-det vs rank) to split lattices into nearly orthogonal stable blocks; proves the Euclidean Kannan–Lovász variant up to polylog factors via reverse-Minkowski/slicing arguments, yielding checkable certificates (coNT up to constants) and suggesting an n^{n/2}‑type speedup for IP under a symmetrization conjecture.

AI-written summary · about

" chapters (16)

1. 0:00Intro
2. 0:14Outline 1. Integer Programming and the Kannan-Lovász (KL) Conjecture.
3. 1:20Integer Programming (IP)
4. 4:05Lattice Point Enumeration
5. 10:24IP Algorithm: "Flat" body case
6. 14:56Kannan-Lovász Theorem [KL 88]
7. 17:58Kannan-Lovász Conjecture [KL 88]
8. 23:24Covering Radius Problem (CRP) a-GapCRP: Input lattice L(B), t 0 Yes Instance: (L) St
9. 29:33Notation
10. 30:23Volumetric Lower Bounds
11. 35:31Canonical Polygon Stuhler 76
12. 40:14Canonical Filtration Stuhler 76 n dimensional lattice L
13. 49:09P2 KL vs Slicing Conjecture
14. 52:42Reverse Minkowski Constant
15. 53:31New Lower Bounds from Chains
16. 57:46Open Problems

" related talks

• 01h 01mNearest Neighbor Methods IIIlya Razenshteyn · Foundations of Data Science Boot Camp 2018
• 47mSuccinct Representations and Efficient Algorithms Based on Linear ProgrammingSudipto Guha · Workshop on Succinct Data Representations and Applications (Simons Institute Big Data 2013)
• 42mLearning What Works Best WhenSwati Gupta · Real-Time Decision Making 2018
• 01h 34mAlgorithmic High-Dimensional Geometry IIAlex Andoni · Big Data Boot Camp 2013
• 44mStructured Sparsity-Inducing Norms Through Submodular FunctionsFrancis Bach · Workshop on Succinct Data Representations and Applications (Simons Institute Big Data 2013)
• 35mLocal Statistics, Semidefinite Programming, and Community Detection IISidhanth Mohanty · Computational Phase Transitions (Simons Institute, 2020)
• 57mHigh Dimensional Geometry and Concentration ISantosh Vempala · Foundations of Data Science Boot Camp 2018
• 42mDimensionality Reduction Via Sparse MatricesJelani Nelson · Workshop on Succinct Data Representations and Applications (Simons Institute Big Data 2013)