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.
Publisher Copyright:
© 2017 ACM.
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 -