The Euclidean Distortion of Flat Tori

The Euclidean Distortion of Flat Tori
复制标题

平面托里的欧几里得变形

DOI：
--
复制
发表时间：
2010
期刊：
International Workshop and International Workshop on Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques
影响因子：
--
通讯作者：
O. Regev
O. Regev
中科院分区：
--
文献类型：
--
作者：
I. Haviv;O. Regev

文献摘要

被引文献

相似文献

我们证明了对于每个n维晶格L，环面Rn/L可以以O（n<s:1>√logn）的畸变嵌入到希尔伯特空间中。这改进了Khot和Naor （FOCS 2005, Math）提出的O（n3n/2）的指数上限。Annal. 2006)，并且接近它们的下界Ω（√n）。我们也得到了某些格族的紧界。
We show that for every n-dimensional lattice L the torus Rn/L can be embedded with distortion O(nċ√logn) into a Hilbert space. This improves the exponential upper bound of O(n3n/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 ∈ Rn/L to a Gaussian function centered at u in the Hilbert space L2(Rn/L). The proofs involve Gaussian measures on lattices, the smoothing parameter of lattices and Korkine-Zolotarev bases.