A reverse Minkowski theorem. Regev, O. & Stephens-Davidowitz, N. In STOC, 2017. Paper Tcs+ talk Ias talk Bourbaki seminar abstract bibtex 91 downloads $ \newcommand{\R}{ℝ} \newcommand{łat}{\mathcal{L}} $We prove a conjecture due to Dadush, showing that if $łat ⊂ \R^n$ is a lattice such that $\det(łat') \ge 1$ for all sublattices $łat' ⊆ łat$, then \[∑ \exp(-t^2 \| y\|^2) łe 3/2 , \] where $t := 10(łog n + 2)$ and the sum is over all $y ∈ L$. From this we also derive bounds on the number of short lattice vectors and on the covering radius.
@inproceedings{RSReverseMinkowski17,
title = {A reverse Minkowski theorem},
abstract = {$ \newcommand{\R}{\mathbb{R}} \newcommand{\lat}{\mathcal{L}} $We prove a conjecture due to Dadush, showing that if $\lat \subset \R^n$ is a lattice such that $\det(\lat') \ge 1$ for all sublattices $\lat' \subseteq \lat$, then \[\sum \exp(-t^2 \| y\|^2) \le 3/2 \; , \] where $t := 10(\log n + 2)$ and the sum is over all $y \in L$. From this we also derive bounds on the number of short lattice vectors and on the covering radius.},
url = {http://arxiv.org/abs/1611.05979},
booktitle = {STOC},
author = {Regev, Oded and {Stephens-Davidowitz}, Noah},
year = {2017},
url_TCS+_talk = {http://www.youtube.com/watch?v=mgDNeg3U5TQ},
url_IAS_talk = {http://www.youtube.com/watch?v=9mvPxAKj5BU},
url_Bourbaki_seminar = {http://www.youtube.com/watch?v=j7YvtVvv3qs},
}
Downloads: 91
{"_id":"FsckjeKxZAohQ7ujJ","bibbaseid":"regev-stephensdavidowitz-areverseminkowskitheorem-2017","downloads":91,"creationDate":"2018-05-30T22:56:10.559Z","title":"A reverse Minkowski theorem","author_short":["Regev, O.","Stephens-Davidowitz, N."],"year":2017,"bibtype":"inproceedings","biburl":"https://dl.dropboxusercontent.com/s/fdsagwnpu86ikr5/bibbase_published.bib","bibdata":{"bibtype":"inproceedings","type":"inproceedings","title":"A reverse Minkowski theorem","abstract":"$ \\newcommand{\\R}{ℝ} \\newcommand{łat}{\\mathcal{L}} $We prove a conjecture due to Dadush, showing that if $łat ⊂ \\R^n$ is a lattice such that $\\det(łat') \\ge 1$ for all sublattices $łat' ⊆ łat$, then \\[∑ \\exp(-t^2 \\| y\\|^2) łe 3/2 , \\] where $t := 10(łog n + 2)$ and the sum is over all $y ∈ L$. From this we also derive bounds on the number of short lattice vectors and on the covering radius.","url":"http://arxiv.org/abs/1611.05979","booktitle":"STOC","author":[{"propositions":[],"lastnames":["Regev"],"firstnames":["Oded"],"suffixes":[]},{"propositions":[],"lastnames":["Stephens-Davidowitz"],"firstnames":["Noah"],"suffixes":[]}],"year":"2017","url_tcs+_talk":"http://www.youtube.com/watch?v=mgDNeg3U5TQ","url_ias_talk":"http://www.youtube.com/watch?v=9mvPxAKj5BU","url_bourbaki_seminar":"http://www.youtube.com/watch?v=j7YvtVvv3qs","bibtex":"@inproceedings{RSReverseMinkowski17,\n title = {A reverse Minkowski theorem},\n abstract = {$ \\newcommand{\\R}{\\mathbb{R}} \\newcommand{\\lat}{\\mathcal{L}} $We prove a conjecture due to Dadush, showing that if $\\lat \\subset \\R^n$ is a lattice such that $\\det(\\lat') \\ge 1$ for all sublattices $\\lat' \\subseteq \\lat$, then \\[\\sum \\exp(-t^2 \\| y\\|^2) \\le 3/2 \\; , \\] where $t := 10(\\log n + 2)$ and the sum is over all $y \\in L$. From this we also derive bounds on the number of short lattice vectors and on the covering radius.},\n url = {http://arxiv.org/abs/1611.05979},\n booktitle = {STOC},\n author = {Regev, Oded and {Stephens-Davidowitz}, Noah},\n year = {2017},\n url_TCS+_talk = {http://www.youtube.com/watch?v=mgDNeg3U5TQ},\n url_IAS_talk = {http://www.youtube.com/watch?v=9mvPxAKj5BU},\n url_Bourbaki_seminar = {http://www.youtube.com/watch?v=j7YvtVvv3qs},\n}\n\n","author_short":["Regev, O.","Stephens-Davidowitz, N."],"key":"RSReverseMinkowski17","id":"RSReverseMinkowski17","bibbaseid":"regev-stephensdavidowitz-areverseminkowskitheorem-2017","role":"author","urls":{"Paper":"http://arxiv.org/abs/1611.05979"," tcs+ talk":"http://www.youtube.com/watch?v=mgDNeg3U5TQ"," ias talk":"http://www.youtube.com/watch?v=9mvPxAKj5BU"," bourbaki seminar":"http://www.youtube.com/watch?v=j7YvtVvv3qs"},"metadata":{"authorlinks":{"stephens-davidowitz, n":"https://noahsd.com/gpt-test/index.html"}},"downloads":91},"search_terms":["reverse","minkowski","theorem","regev","stephens-davidowitz"],"keywords":[],"authorIDs":["NsKfZS8svvuZwZEBa"],"dataSources":["kxAEBDHXGfX8ATRE5","HhrFT8C8XJdJggbxX","DFNYHMG5naiXCbQWf","t7S757akkuDKXd4Lt"]}