A reverse Minkowski theorem. Regev, O. & Stephens-Davidowitz, N. In STOC, 2017.
A reverse Minkowski theorem [link]Paper  A reverse Minkowski theorem [link]Tcs+ talk  A reverse Minkowski theorem [link]Ias talk  A reverse Minkowski theorem [link]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