A reverse minkowski theorem

Oded Regev; Noah Stephens-Davidowitz

doi:10.1145/3055399.3055434

A reverse minkowski theorem

Oded Regev, Noah Stephens-Davidowitz

Computer Science

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Abstract

We prove a conjecture due to Dadush, showing that if L ⊂ ℝⁿ 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 language	English (US)
Title of host publication	STOC 2017 - Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing
Editors	Pierre McKenzie, Valerie King, Hamed Hatami
Publisher	Association for Computing Machinery
Pages	941-953
Number of pages	13
ISBN (Electronic)	9781450345286
DOIs	https://doi.org/10.1145/3055399.3055434
State	Published - Jun 19 2017
Event	49th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2017 - Montreal, Canada Duration: Jun 19 2017 → Jun 23 2017

Publication series

Name	Proceedings of the Annual ACM Symposium on Theory of Computing
Volume	Part F128415
ISSN (Print)	0737-8017

Other

Other	49th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2017
Country/Territory	Canada
City	Montreal
Period	6/19/17 → 6/23/17

Keywords

Geometry of numbers
Lattices

ASJC Scopus subject areas

Software

Access to Document

10.1145/3055399.3055434

Cite this

Regev, O., & Stephens-Davidowitz, N. (2017). A reverse minkowski theorem. In P. McKenzie, V. King, & H. Hatami (Eds.), STOC 2017 - Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing (pp. 941-953). (Proceedings of the Annual ACM Symposium on Theory of Computing; Vol. Part F128415). Association for Computing Machinery. https://doi.org/10.1145/3055399.3055434

A reverse minkowski theorem. / Regev, Oded; Stephens-Davidowitz, Noah.
STOC 2017 - Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing. ed. / Pierre McKenzie; Valerie King; Hamed Hatami. Association for Computing Machinery, 2017. p. 941-953 (Proceedings of the Annual ACM Symposium on Theory of Computing; Vol. Part F128415).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Regev, O & Stephens-Davidowitz, N 2017, A reverse minkowski theorem. in P McKenzie, V King & H Hatami (eds), STOC 2017 - Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing. Proceedings of the Annual ACM Symposium on Theory of Computing, vol. Part F128415, Association for Computing Machinery, pp. 941-953, 49th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2017, Montreal, Canada, 6/19/17. https://doi.org/10.1145/3055399.3055434

@inproceedings{1de9ae84e32d4d1f908f10e644f7745c,

title = "A reverse minkowski theorem",

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.",

keywords = "Geometry of numbers, Lattices",

author = "Oded Regev and Noah Stephens-Davidowitz",

note = "Publisher Copyright: {\textcopyright} 2017 ACM.; 49th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2017 ; Conference date: 19-06-2017 Through 23-06-2017",

year = "2017",

month = jun,

day = "19",

doi = "10.1145/3055399.3055434",

language = "English (US)",

series = "Proceedings of the Annual ACM Symposium on Theory of Computing",

publisher = "Association for Computing Machinery",

pages = "941--953",

editor = "Pierre McKenzie and Valerie King and Hamed Hatami",

booktitle = "STOC 2017 - Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing",

}

TY - GEN

T1 - A reverse minkowski theorem

AU - Regev, Oded

AU - Stephens-Davidowitz, Noah

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 -

A reverse minkowski theorem

Abstract

Publication series

Other

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this