LIPIcs.APPROX-RANDOM.2020.43.pdf
- Filesize: 493 kB
- 14 pages
Document
Nearly Optimal Embeddings of Flat Tori
Authors
-
Part of:
Volume:
Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2020)
Series: Leibniz International Proceedings in Informatics (LIPIcs)
Conference: International Conference on Randomization and Computation (RANDOM)
Conference: International Conference on Approximation Algorithms for Combinatorial Optimization Problems (APPROX) - License:
Creative Commons Attribution 3.0 Unported license
- Publication Date: 2020-08-11
File
Document Identifiers
Cite AsGet BibTex
Ishan Agarwal, Oded Regev, and Yi Tang. Nearly Optimal Embeddings of Flat Tori. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 176, pp. 43:1-43:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
https://doi.org/10.4230/LIPIcs.APPROX/RANDOM.2020.43
https://doi.org/10.4230/LIPIcs.APPROX/RANDOM.2020.43
Abstract
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).
Subject Classification
ACM Subject Classification
- Mathematics of computing → Discrete mathematics
Keywords
- Lattices
- metric embeddings
- flat torus
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads
References
- Ishay Haviv and Oded Regev. The Euclidean distortion of flat tori. J. Topol. Anal., 5(2):205-223, 2013. Preliminary version in APPROX 2010. URL: https://doi.org/10.1142/S1793525313500064.
-
Piotr Indyk. Algorithmic applications of low-distortion geometric embeddings. In 42nd IEEE Symposium on Foundations of Computer Science (Las Vegas, NV, 2001), pages 10-33. IEEE Computer Soc., Los Alamitos, CA, 2001.
- Subhash Khot and Assaf Naor. Nonembeddability theorems via Fourier analysis. Math. Ann., 334(4):821-852, 2006. Preliminary version in FOCS 2005. URL: https://doi.org/10.1007/s00208-005-0745-0.
-
John Milnor and Dale Husemoller. Symmetric bilinear forms. Springer-Verlag, New York-Heidelberg, 1973. Ergebnisse der Mathematik und ihrer Grenzgebiete, Band 73.