Towards strong reverse Minkowski-type inequalities for lattices
Presented at the Annual IEEE Symposium on Foundations of Computer Science (October 2016), New Brunswick, Canada
We present a natural reverse Minkowski-type inequality for lattices, which gives upper bounds on the number of lattice points in a Euclidean ball in terms of sublattice determinants, and conjecture its optimal form. The conjecture exhibits a surprising wealth of connections to various areas in mathematics and computer science, including a conjecture motivated by integer programming by Kannan and Lov\'asz (Annals of Math. 1988), a question from additive combinatorics asked by Green, a question on Brownian motions asked by Saloff-Coste (Colloq. Math. 2010), a theorem by Milman and Pisier from convex geometry (Ann. Probab. 1987), worst-case to average-case reductions in lattice-based cryptography, and more. We present these connections, provide evidence for the conjecture, and discuss possible approaches towards a proof. Our main technical contribution is in proving that our conjecture implies the ℓ2 case of the Kannan and Lov\'asz conjecture. The proof relies on a novel convex relaxation for the covering radius, and a rounding procedure for based on "uncrossing" lattice subspaces.
|Annual IEEE Symposium on Foundations of Computer Science|
|Organisation||Networks and Optimization|
Dadush, D.N, & Regev, O. (2016). Towards strong reverse Minkowski-type inequalities for lattices. In Annual IEEE Symposium on Foundations of Computer Science (pp. 447–456). doi:10.1109/FOCS.2016.55