|
|
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. |
|