2026-07-21T02:34:26Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:12646 2024-03-06T10:51:20Z ddc:004 open_access

Nearly Optimal Embeddings of Flat Tori Agarwal, Ishan Regev, Oded Tang, Yi Lattices metric embeddings flat torus We show that for any n-dimensional lattice ℒ ⊆ ℝⁿ, the torus ℝⁿ/ℒ 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). Schloss Dagstuhl – Leibniz-Zentrum für Informatik Ishan Agarwal and Oded Regev and Yi Tang 2020 Is Part Of LIPIcs, Volume 176, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2020) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.APPROX/RANDOM.2020.43 urn:nbn:de:0030-drops-126464 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2020.43 eng https://creativecommons.org/licenses/by/3.0/legalcode