Can I read Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing - STOC 2019 - On approximating the covering radius and finding dense lattice subspaces on EtoBox?

Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing - STOC 2019 - On approximating the covering radius and finding dense lattice subspaces by Dadush, Daniel is a scholarly article available to read on EtoBox.

What is Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing - STOC 2019 - On approximating the covering radius and finding dense lattice subspaces about?

In this work, we give a novel algorithm for computing dense lattice subspaces, a conjecturally tight characterization of the lattice covering radius, and provide a bound on the slicing constant of lattice Voronoi cells. Our work is motivated by the pursuit of faster algorithms for integer programming, for which we give a conditional speedup based on the recent resolution of the l 2 Kannan-Lovász conjecture. Through these results, we hope to motivate further study of the interplay between the recently developed reverse Minkowski theory, lattice algorithms and convex geometry. On the algorithmic side, our main contribution is a 2 O (n) -time algorithm for computing a O(C η (n))-approximate sublattice of minimum normalized determinant on any n-dimensional lattice, where C η (n) = O(log n) is the reverse Minkowski constant in dimension n.

Author

Dadush, Daniel

Publisher

ACM Press

Published

2019

Language

EN