Publication View

Abstract (2008)

Abstract
Various new nonembeddability results (mainly into L1) are proved via Fourier analysis. In particular, it is shown that the Edit Distance on {0, 1} d has L1 distortion Ω ( � log d / log log d). We also give new lower bounds on the L1 distortion of flat tori, quotients of the discrete hypercube under group actions, and the transportation cost (Earthmover) metric. 1

Publication details
Download http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.92.1022
Source http://research.microsoft.com/research/theory/naor/homepage files/nonembed-final.pdf
Contributors CiteSeerX
Repository CiteSeerX - Scientific Literature Digital Library and Search Engine (United States)
Type text
Language English
Relation 10.1.1.44.5650, 10.1.1.40.6984, 10.1.1.135.9318, 10.1.1.3.9509, 10.1.1.22.108, 10.1.1.130.9013, 10.1.1.20.723, 10.1.1.16.183, 10.1.1.35.8576, 10.1.1.129.7422, 10.1.1.37.5438, 10.1.1.124.9739, 10.1.1.111.7659, 10.1.1.53.5438, 10.1.1.95.2079, 10.1.1.114.5693, 10.1.1.17.5556, 10.1.1.46.9488, 10.1.1.10.6494, 10.1.1.42.342, 10.1.1.30.4514, 10.1.1.136.6387, 10.1.1.130.2482, 10.1.1.40.2201, 10.1.1.24.6027, 10.1.1.20.9522, 10.1.1.79.5078, 10.1.1.55.3936, 10.1.1.33.9778, 10.1.1.126.760, 10.1.1.57.3548, 10.1.1.57.5561, 10.1.1.11.8391, 10.1.1.11.2242, 10.1.1.137.6057, 10.1.1.123.2592, 10.1.1.133.5651, 10.1.1.101.8611, 10.1.1.35.9865, 10.1.1.16.9786, 10.1.1.26.2130, 10.1.1.25.2676, 10.1.1.43.9283, 10.1.1.3.7975, 10.1.1.91.7370, 10.1.1.130.3650, 10.1.1.100.9576, 10.1.1.41.4493, 10.1.1.13.1035, 10.1.1.36.2374, 10.1.1.37.5552, 10.1.1.18.8246, 10.1.1.36.5766, 10.1.1.43.6084, 10.1.1.13.2391, 10.1.1.2.7184, 10.1.1.22.2899, 10.1.1.135.4919, 10.1.1.104.2928, 10.1.1.37.432, 10.1.1.136.3918, 10.1.1.114.3093, 10.1.1.22.839, 10.1.1.31.7587, 10.1.1.16.5310, 10.1.1.39.7253, 10.1.1.36.8615, 10.1.1.12.2122, 10.1.1.17.4424, 10.1.1.111.1256, 10.1.1.4.37, 10.1.1.54.1347, 10.1.1.78.6784, 10.1.1.10.552, 10.1.1.132.6117, 10.1.1.50.5312, 10.1.1.41.2251, 10.1.1.118.5093, 10.1.1.46.4230, 10.1.1.132.9985, 10.1.1.111.8540, 10.1.1.12.8553, 10.1.1.8.4878, 10.1.1.123.265, 10.1.1.120.699, 10.1.1.68.3781, 10.1.1.36.5090, 10.1.1.12.7251, 10.1.1.9.5806, 10.1.1.22.2091, 10.1.1.36.6521, 10.1.1.106.170, 10.1.1.67.4295, 10.1.1.36.5939, 10.1.1.1.2455, 10.1.1.25.2971, 10.1.1.69.4425, 10.1.1.85.8775, 10.1.1.19.3301, 10.1.1.102.6948, 10.1.1.110.9789, 10.1.1.125.2382, 10.1.1.35.7871, 10.1.1.54.4646, 10.1.1.5.2839, 10.1.1.123.1190, 10.1.1.69.743, 10.1.1.99.3501, 10.1.1.3.9445, 10.1.1.2.9055