Nearly optimal embeddings of flat tori

Ishan Agarwal, Oded Regev, Yi Tang

Research output: Chapter in Book/Report/Conference proceedingConference contribution

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).

Original languageEnglish (US)
Title of host publicationApproximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX/RANDOM 2020
EditorsJaroslaw Byrka, Raghu Meka
PublisherSchloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
ISBN (Electronic)9783959771641
DOIs
StatePublished - Aug 1 2020
Event23rd International Conference on Approximation Algorithms for Combinatorial Optimization Problems and 24th International Conference on Randomization and Computation, APPROX/RANDOM 2020 - Virtual, Online, United States
Duration: Aug 17 2020Aug 19 2020

Publication series

NameLeibniz International Proceedings in Informatics, LIPIcs
Volume176
ISSN (Print)1868-8969

Conference

Conference23rd International Conference on Approximation Algorithms for Combinatorial Optimization Problems and 24th International Conference on Randomization and Computation, APPROX/RANDOM 2020
CountryUnited States
CityVirtual, Online
Period8/17/208/19/20

Keywords

  • Flat torus
  • Lattices
  • Metric embeddings

ASJC Scopus subject areas

  • Software

Fingerprint Dive into the research topics of 'Nearly optimal embeddings of flat tori'. Together they form a unique fingerprint.

  • Cite this

    Agarwal, I., Regev, O., & Tang, Y. (2020). Nearly optimal embeddings of flat tori. In J. Byrka, & R. Meka (Eds.), Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX/RANDOM 2020 [APPROX43] (Leibniz International Proceedings in Informatics, LIPIcs; Vol. 176). Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing. https://doi.org/10.4230/LIPIcs.APPROX/RANDOM.2020.43