A reverse minkowski theorem

Oded Regev, Noah Stephens-Davidowitz

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

Abstract

We prove a conjecture due to Dadush, showing that if L ⊂ ℝn is a lattice such that det(L′) ≥ 1 for all sublattices L′ ⊆ L, then (Equation presented), where t:= 10(log n + 2). From this we also derive bounds on the number of short lattice vectors and on the covering radius.

Original languageEnglish (US)
Title of host publicationSTOC 2017 - Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing
EditorsPierre McKenzie, Valerie King, Hamed Hatami
PublisherAssociation for Computing Machinery
Pages941-953
Number of pages13
ISBN (Electronic)9781450345286
DOIs
StatePublished - Jun 19 2017
Event49th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2017 - Montreal, Canada
Duration: Jun 19 2017Jun 23 2017

Publication series

NameProceedings of the Annual ACM Symposium on Theory of Computing
VolumePart F128415
ISSN (Print)0737-8017

Other

Other49th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2017
Country/TerritoryCanada
CityMontreal
Period6/19/176/23/17

Keywords

  • Geometry of numbers
  • Lattices

ASJC Scopus subject areas

  • Software

Cite this