Department of Computer Science | Institute of Theoretical Computer Science | CADMO

Theory of Combinatorial Algorithms

Prof. Emo Welzl and Prof. Bernd Gärtner

Metric Embeddings - FS 2010
Theory of Combinatorial Algorithms Institute of Theoretical Computer Science Department of Computer Science ETH Zurich

Metric Embeddings - FS 2010

Abstract of the course

A basic question in metric embeddings is: How well can we represent a given finite metric space in a Euclidean space, say? This area has been developing very intensively in recent years, and it has provided the best known approximation algorithms for several hard computational problems. From a mathematical point of view, we will cover several geometric, probabilistic, and combinatorial techniques.

At the end of the course, the students are expected to be familiar with the basic concepts, techniques, results, and open problems in the field of low-distortion embeddings and prepared to read the current literature on the subject.

Time & Place

Instructors

Lecturer:
Uli Wagner (first half of the course)
 CAB G 33.2/ Tel: (044) 632-7339. e-mail: 
Jiri Matousek (second half of the course)
 e-mail: 
Assistant:
Gabriel Nivasch
 CAB G 37.1/ Tel: (044) 632-7372. email: 

Language

English

Grades

The final exam will account for 70% of the final grade, and the homework exercises will account for the remaining 30%.

Exam

There will be a 30-minute oral exam at the end of the semester. The date will be announced later on.

Exercises

Every second week we will hand out a problem sheet. The written solutions should be submitted two weeks later. It is OK to discuss the exercises with other students, but each student should write up his/her solution individually.

Regulations for Ph.D. students

As per the new department regulations, the same rules apply for Ph.D. students to obtain credit points as for all other participants. It is necessary to take the exam and achieve an overall grade of at least 4.0 in order to qualify for receiving credits. Merely attending the course and/or handing in exercises is no longer sufficient.

Course material

Printed lecture notes wil be distributed in class. Exercises will be posted here as the semester progresses.

Lectures Material covered Exercises

(Uli:)
Week 1 Tue, 23.2 Basic definitions (metric spaces, distortion) and preview of some fundamental results to be proved in the course Problem set 1 (due March 8)
Thu, 25.2 Normed spaces, lp metrics

Week 2 Tue, 2.3 Relations between lp metrics
Thu, 4.3 Topological lower bounds on distortion (for embeddings into lpd with bounded dimension d)

Week 3 Tue, 9.3 Topological lower bounds on distortion (for embeddings into lpd with bounded dimension d) Problem set 2 (due March 22)
Thu, 11.3 Lower bounds on the dimension by counting (for embeddings into lpd, p finite, with bounded distortion)

Week 4 Tue, 16.3 Lower bounds on the dimension by counting (for embeddings into lpd, p finite, with bounded distortion)
Thu, 18.3 Lower bounds on the distortion for embedding expanders into lp, 1 ≤ p ≤ 2

Week 5 Tue, 23.3 Lower bounds on the distortion for embedding expanders into lp, 1 ≤ p ≤ 2 Problem set 3 (due April 12)
Thu, 25.3 Lower bounds on the distortion for embedding expanders into lp, 1 ≤ p ≤ 2

Week 6 Tue, 30.3 Upper bounds for distortion vs. dimension for embeddings into l.
Bourgain's theorem for embeddings into Eucldean spaces.

(Jirka:)
Week 7 Tue, 13.4 An O(log n) approximation for the sparsest cut problem via Bourgain's theorem.
Thu, 15.4 Metrics of negative type, and how they appear in a better approximation algorithm for the sparsest cut.
Analysis of Boolean functions - an introduction: the Fourier coefficients, influences.

Week 8 Tue, 20.4 Statement of the KKL theorem, a hypercontractive inequality. Problem set 4 (due May 3)
Thu, 22.4 Proof of the KKL theorem. Introduction to edit distance, lower bound for embedding the edit distance in l1.

Week 9 Tue, 27.4 Finishing the proof of the lower bound. Introduction to the Johnson-Lindenstrauss lemma and random projections.
Thu, 29.4 Normal distribution, its 2-stability, random variables with subgaussian tails, the moment generating function, and how it can be used to prove subgaussian tails.

Week 10 Tue, 4.5 The random projection lemma for the Gaussian case. Problem set 5 (due May 17)
Thu, 6.5 Embedding the n-dimensional Euclidean space in O(n)-dimensional l1.
Introduction to stream computations, the l2 norm estimate problem.

Week 11 Tue, 11.5 Nisan's pseudorandom generator.

Week 12 Tue, 18.5 A randomized streaming algorithm for l2 norm estimation. Problem set 6 (due May 31)
Thu, 20.5 Explicit embeddings of Euclidean spaces in l1.

Week 13 Tue, 25.5 The nearest neighbor problem.
Thu, 27.5 Locality-sensitive hashing.

Week 14 Tue, 1.6 Locality-sensitive hasing.
Thu, 3.6 Guest lecturer: Anastasios Sidiropoulos, Computational aspects of low-distortion embeddings.

Literature


Last edited: June 28, 2010
Gabriel Nivasch