TY - GEN
T1 - Nonembeddability theorems via Fourier analysis
AU - Khot, Subhash
AU - Naor, Assaf
PY - 2005
Y1 - 2005
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-o(1) We also give new lower bounds on the L 1 distortion of 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-o(1) We also give new lower bounds on the L 1 distortion of quotients of the discrete hypercube under group actions, and the transportation cost (Earthmover) metric.
UR - http://www.scopus.com/inward/record.url?scp=33748586226&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=33748586226&partnerID=8YFLogxK
U2 - 10.1109/SFCS.2005.54
DO - 10.1109/SFCS.2005.54
M3 - Conference contribution
AN - SCOPUS:33748586226
SN - 0769524680
SN - 9780769524689
T3 - Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS
SP - 101
EP - 110
BT - Proceedings - 46th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2005
T2 - 46th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2005
Y2 - 23 October 2005 through 25 October 2005
ER -