Nearly Optimal Embeddings of Flat Tori

Abstract

We show that for any $n$-dimensional lattice $\mathcal{L}\subseteq {\mathbb{R}}^n$, the torus ${\mathbb{R}}^n/\mathcal{L}$ can be embedded into Hilbert space with $O(\sqrt{n\log n})$ distortion. This improves the previously best known upper bound of $O(n\sqrt{\log n})$ shown by Haviv and Regev (APPROX 2010) and approaches the lower bound of $\Omega (\sqrt{n})$ due to Khot and Naor (FOCS 2005, Math. Annal. 2006).

14 pages