@inproceedings{7a90e8f32bdf4fef8ab1cd1461edb0ab,
title = "The Euclidean distortion of flat tori",
abstract = "We show that for every n-dimensional lattice ℒ the torus ℝn/ℒ can be embedded with distortion O(n·√log n) into a Hilbert space. This improves the exponential upper bound of O(n 3n/2) due to Khot and Naor (FOCS 2005, Math. Annal. 2006) and gets close to their lower bound of Ω(√n). We also obtain tight bounds for certain families of lattices. Our main new ingredient is an embedding that maps any point u ∈ ℝn/ℒ to a Gaussian function centered at u in the Hilbert space L2ℝn/ℒ. The proofs involve Gaussian measures on lattices, the smoothing parameter of lattices and Korkine-Zolotarev bases.",
keywords = "Embedding, Lattice, Torus",
author = "Ishay Haviv and Oded Regev",
year = "2010",
doi = "10.1007/978-3-642-15369-3_18",
language = "English (US)",
isbn = "3642153682",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
pages = "232--245",
booktitle = "Approximation, Randomization, and Combinatorial Optimization",
note = "13th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2010 and 14th International Workshop on Randomization and Computation, RANDOM 2010 ; Conference date: 01-09-2010 Through 03-09-2010",
}