Nonembeddability theorems via Fourier analysis

Simple item page
dc.creatorKhot, Subhash
dc.creatorNaor, Assaf
dc.date2005-10-26
dc.date.accessioned2026-07-07T06:47:54Z
dc.date.available2026-07-07T06:47:54Z
dc.descriptionVarious new nonembeddability results (mainly into $L_1$) are proved via Fourier analysis. In particular, it is shown that the Edit Distance on $\{0,1\}^d$ has $L_1$ distortion $(\log d)^{\frac12-o(1)}$. We also give new lower bounds on the $L_1$ distortion of flat tori, quotients of the discrete hypercube under group actions, and the transportation cost (Earthmover) metric.
dc.descriptionWith an appendix on quantitative estimates in Bourgain's noise sensitivity theorem. To appear in Mathematiche Annalen. An extended abstract appeared in FOCS 2005
dc.identifierhttps://arxiv.org/abs/math/0510547
dc.identifierhttp://arxiv.org/abs/math/0510547
dc.identifier.urihttp://salesiana.dossiersoluciones.com/handle/123456789/103807
dc.subjectFunctional Analysis
dc.subjectMetric Geometry
dc.subject46B20; 68U05
dc.titleNonembeddability theorems via Fourier analysis
dc.typetext

Files

Collections

arXiv