TY - GEN

T1 - A reverse minkowski theorem

AU - Regev, Oded

AU - Stephens-Davidowitz, Noah

N1 - Funding Information:
Supported by the Simons Collaboration on Algorithms and Geometry and by the National Science Foundation (NSF) under Grant No. CCF-1320188. Any opinions, findings, and conclusions or recommendations expressed in this material are those of the authors and do not necessarily reflect the views of the NSF. Supported by the National Science Foundation (NSF) under Grant No. CCF-1320188, and the Defense Advanced Research Projects Agency (DARPA) and Army Research Office (ARO) under Contract No. W911NF-15-C-0236. Part of this work was done while visiting Chris Peikert at the University of Michigan.

PY - 2017/6/19

Y1 - 2017/6/19

N2 - 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.

AB - 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.

KW - Geometry of numbers

KW - Lattices

UR - http://www.scopus.com/inward/record.url?scp=85022095564&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85022095564&partnerID=8YFLogxK

U2 - 10.1145/3055399.3055434

DO - 10.1145/3055399.3055434

M3 - Conference contribution

AN - SCOPUS:85022095564

T3 - Proceedings of the Annual ACM Symposium on Theory of Computing

SP - 941

EP - 953

BT - STOC 2017 - Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing

A2 - McKenzie, Pierre

A2 - King, Valerie

A2 - Hatami, Hamed

PB - Association for Computing Machinery

T2 - 49th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2017

Y2 - 19 June 2017 through 23 June 2017

ER -