@inproceedings{8a7eafb0ce4a43d89cc8d4dc211dd062,
title = "Nearly optimal embeddings of flat tori",
abstract = "We show that for any n-dimensional lattice L ⊆ Rn, the torus Rn/L can be embedded into Hilbert space with O(√nlog n) distortion. This improves the previously best known upper bound of O(n√log n) shown by Haviv and Regev (APPROX 2010, J. Topol. Anal. 2013) and approaches the lower bound of Ω(√n) due to Khot and Naor (FOCS 2005, Math. Ann. 2006).",
keywords = "Flat torus, Lattices, Metric embeddings",
author = "Ishan Agarwal and Oded Regev and Yi Tang",
note = "Publisher Copyright: {\textcopyright} 2020 Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing. All rights reserved.; 23rd International Conference on Approximation Algorithms for Combinatorial Optimization Problems and 24th International Conference on Randomization and Computation, APPROX/RANDOM 2020 ; Conference date: 17-08-2020 Through 19-08-2020",
year = "2020",
month = aug,
day = "1",
doi = "10.4230/LIPIcs.APPROX/RANDOM.2020.43",
language = "English (US)",
series = "Leibniz International Proceedings in Informatics, LIPIcs",
publisher = "Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing",
editor = "Jaroslaw Byrka and Raghu Meka",
booktitle = "Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX/RANDOM 2020",
}