Nearly Optimal Embeddings of Flat Tori

We show that for any $n$-dimensional lattice $$\mathcal{L}$ \subseteq $\mathbb{R}$^n$,thetorus$$\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 $\mathrm{\Omega }(\sqrt{n})$ due to Khot and Naor (FOCS 2005, Math. Annal. 2006).