2019-06-23

# On approximating the covering radius and finding dense lattice subspaces

## Publication

### Publication

*Presented at the Annual ACM SIGACT Symposium on Theory of Computing (June 2019), New York, New York, USA*

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 ℓ_{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(logn) is the reverse Minkowski constant in dimension n. Our method for finding dense lattice subspaces is surprisingly simple: we iteratively descend to a random co-dimension 1 subspace chosen to be the orthogonal space to a discrete Gaussian sample from the dual lattice. Applying this algorithm within a “filtration reduction” scheme, we further show how to compute a O(C_{η}(n))-approximate canonical filtration of any lattice, which corresponds to a canonical way of decomposing a lattice into dense blocks. As a primary application, we get the first 2^{O(n)}-time algorithm for computing a sparse lattice projection whose “volume radius” provides a lower bound on the lattice covering radius that is tight within a O(log^{2.5} n)-factor. This provides an efficient algorithmic version of the ℓ_{2} Kannan-Lovász conjecture, which was recently resolved by Regev and Stephens-Davidowitz (STOC’2017).

On the structural side, we prove a new lower bound on the covering radius which combines volumetric lower bounds across a chain of lattice projections. Assuming Bourgain’s slicing conjecture restricted to Voronoi cells of stable lattices, our lower bound implies (somewhat surprisingly) that the problem of approximating the lattice covering radius to within a constant factor is in coNP. Complementing this result, we show that the slicing constant of any n-dimensional Voronoi cell is bounded by O(C_{KL,2}(n)) = O(log^{1.5} n), the ℓ_{2} Kannan-Lovász constant, which complements the O(log n) bound of Regev and Stephens-Davidowitz for stable Voronoi cells.

Additional Metadata | |
---|---|

Integer Programming, Kannan-Lovász Conjecture, Lattice Problems | |

doi.org/10.1145/3313276.3316397 | |

Annual ACM SIGACT Symposium on Theory of Computing | |

Organisation | Centrum Wiskunde & Informatica, Amsterdam, The Netherlands |

Dadush, D.N. (2019). On approximating the covering radius and finding dense lattice subspaces. In
Proceedings of the Annual ACM SIGACT Symposium on Theory of Computing (pp. 1021–1026). doi:10.1145/3313276.3316397 |