This seminar is directed at students enrolled in the Mathematics Master as well as students enrolled in the Computer Science Master. The kick-off meeting for the seminar will take place on Wednesday, April 3rd, 2019, at 10:15 am, in room 2.078 in the Computer Science Building at Endenicher Allee 19 A.

The task is as follows:

• Studying a scientific paper (Topics below)
• Presentation in a talk (30 Minutes, dates below)
• Written report (in own words) 10 pages

An n-point metric space (X,D) is an n-set X and a metric D, which can be defined by a table of distances between pairs of points of X. Metric embeddings provide compact representations for such metric spaces while at the same time preserving the metric up to some distortion. Such representations have numerous applications in computer science, if they exist. The starting point of our study is the survey by Indyk and Matousek from 2002 (revised version with Sidiropoulos from 2017). The plan is to study some fundamental results described in the survey together with more recent literature in the state of the art of the field.

Individual Topics

• Bourgain's embedding (Sec 8.2.1 in [1] and Sec 15.6-15.7 in [2])
• Lower bounds by counting (Sec 15.3. in [2] and [10])
• Johnson-Lindenstrauss Lemma (Sec 8.2.4. in [1] and Sec 15.2 in [2])
• Volume-respecting embeddings (Sec 8.2.6 in [1] and [9])
• Planar-graph metrics (Sec 8.3.1 in [1] and [8])
• Probabilistic embeddings in trees (Sec 8.4.1. in [1] and [6] and [10])
• Embeddings into the line [3]
• Embeddings of Hausdorff metrics [4]
• Embeddings with outliers [5]
• Doubling metrics [7]

1. Piotr Indyk, Jiří Matoušek, and Anastasios Sidiropoulos. „Low-distortion embeddings of finite metric spaces.“ Handbook of Discrete and Computational Geometry, Third Edition. Chapman and Hall/CRC, 2017. 211-231. [PDF]
2. Jirı Matoušek. „Embedding Finite Metric Spaces into Normed Spaces“ In: Jirı Matoušek. Lectures on Discrete Geometry. Springer Verlag, New York, 2002. [PDF]
3. Bǎdoiu, Mihai, Julia Chuzhoy, Piotr Indyk, and Anastasios Sidiropoulos. „Low-distortion embeddings of general metrics into the line.“ Proceedings of the thirty-seventh annual ACM symposium on Theory of computing. ACM, 2005.
4. Backurs, Arturs, and Anastasios Sidiropoulos. „Constant-distortion embeddings of hausdorff metrics into constant-dimensional l_p spaces.“ Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2016).
5. Sidiropoulos, Anastasios, Dingkang Wang, and Yusu Wang. „Metric embeddings with outliers.“ Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms. Society for Industrial and Applied Mathematics, 2017.
6. Fakcharoenphol, Jittat, Satish Rao, and Kunal Talwar. „A tight bound on approximating arbitrary metrics by tree metrics.“ Journal of Computer and System Sciences 69.3 (2004): 485-497.
7. Gupta, Anupam, Robert Krauthgamer, and James R. Lee. „Bounded geometries, fractals, and low-distortion embeddings.“ 44th Annual IEEE Symposium on Foundations of Computer Science, 2003. Proceedings. IEEE, 2003.
8. Rao, Satish. „Small distortion and volume preserving embeddings for planar and Euclidean metrics.“ Proceedings of the Fifteenth Annual Symposium on Computational Geometry. ACM, 1999.
9. Feige, Uriel. „Approximating the bandwidth via volume respecting embeddings.“ Journal of Computer and System Sciences 60.3 (2000): 510-539.
10. Har-Peled, Sariel. „Finite Metric Spaces and Partitions“ In Sariel Har-Peled. Geometric Approximation Algorithms. AMS. 2010
11. Bartal, Yair. „Probabilistic Approximation of Metric Spaces and its Algorithmic Applications“. Proceedings of 37th Conference on Foundations of Computer Science. IEEE, 1996.
12. Moses Charikar, Chandra Chekuri, Ashish Goel, Sudipto Guha, and Serge Plotkin. „Approximating a finite metric by a small number of tree metrics.“ In Proceedings 39th Annual Symposium on Foundations of Computer Science, pp. 379-388. IEEE, 1998.
13. Aumann, Yonatan, and Yuval Rabani. „An O (log k) approximate min-cut max-flow theorem and approximation algorithm.“ SIAM Journal on Computing 27, no. 1 (1998): 291-301.
14. Dimitris Achlioptas, „Database-friendly random projections: Johnson-Lindenstrauss with binary coins“, Journal of Computer and System Sciences, Volume 66, Issue 4, 2003, Pages 671-687.