TY - JOUR
T1 - Nonembeddability theorems via Fourier analysis
AU - Khot, Subhash
AU - Naor, Assaf
PY - 2006/4
Y1 - 2006/4
N2 - Various 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)1/2-0(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.
AB - Various 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)1/2-0(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.
UR - http://www.scopus.com/inward/record.url?scp=33644977894&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=33644977894&partnerID=8YFLogxK
U2 - 10.1007/s00208-005-0745-0
DO - 10.1007/s00208-005-0745-0
M3 - Article
AN - SCOPUS:33644977894
SN - 0025-5831
VL - 334
SP - 821
EP - 852
JO - Mathematische Annalen
JF - Mathematische Annalen
IS - 4
ER -