Prof. Emo Welzl and Prof. Bernd Gärtner
|Mittagsseminar Talk Information|
Date and Time: Thursday, June 23, 2005, 12:15 pm
Duration: This information is not available in the database
Location: This information is not available in the database
Speaker: Jiří Matoušek (Charles Univ.)
The theory of low-distortion embeddings of finite metric spaces has been developing at amazing pace in the last several years, and it has found numerous algorithmic applications. One of the basic questions is, what is the minimum necessary distortion of distances needed for embedding an n-point metric space into a Euclidean space (of unlimited dimension)? The answer, found more than 10 years ago, is of the order log n. Recently Khot and Naor constructed a new example witnessing the lower bound, and proved its bad embeddability by a new approach using a discrete Fourier transform. I will try to explain this. I'm afraid that I will need 50 minutes, even though I will not do everything in detail.
Automatic MiSe System Software Version 1.4803M | admin login