Nonembeddability theorems via Fourier analysis

Various new nonembeddability results (mainly into L/sub 1/) are proved via Fourier analysis. In particular, it is shown that the edit distance on {0, 1}/sup d/ has L/sub 1/ distortion (log d)/sup 1/2 - o(1)/. We also give new lower bounds on the L/sub 1/ distortion of quotients of the discrete hypercube under group actions, and the transportation cost (Earthmover) metric.

Authors

• Subhash Khot
• Assaf Naor

Keywords

• Extraterrestrial measurements
• Hypercubes
• Harmonic analysis
• Transportation
• Costs
• Computer science
• Educational institutions
• Surges
• Computational geometry
• Approximation algorithms
• Fourier Analysis
• Distortion
• Lower Bound
• Quotient
• Transportation Costs
• Edit Distance
• Shortest Path
• Computational Biology
• Banach Space
• Nearest Neighbor Search
• Linear Subspace
• Hausdorff Distance
• Shortest Path Distance
• Cost Metrics