Towards Strong Reverse Minkowski-Type Inequalities for Lattices

Daniel Dadush, Oded Regev

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

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 Lovasz (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 l2 case of the Kannan and Lovasz conjecture. The proof relies on a novel convex relaxation for the covering radius, and a rounding procedure based on 'uncrossing' lattice subspaces.

Original languageEnglish (US)
Title of host publicationProceedings - 57th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2016
PublisherIEEE Computer Society
Pages447-456
Number of pages10
ISBN (Electronic)9781509039333
DOIs
StatePublished - Dec 14 2016
Event57th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2016 - New Brunswick, United States
Duration: Oct 9 2016Oct 11 2016

Publication series

NameProceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS
Volume2016-December
ISSN (Print)0272-5428

Other

Other57th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2016
Country/TerritoryUnited States
CityNew Brunswick
Period10/9/1610/11/16

Keywords

  • Geometry
  • Lattices
  • Minkowski's first theorem

ASJC Scopus subject areas

  • General Computer Science

Fingerprint

Dive into the research topics of 'Towards Strong Reverse Minkowski-Type Inequalities for Lattices'. Together they form a unique fingerprint.

Cite this