CMCS 39600: Theory of Metric Embeddings
Instructor:
Harald Räcke
Course Description:
The analysis of metrics plays an important role in various disciplines
of computer science as e.g. machine learning, data mining or bioinformatics.
This course deals with the theory of metric embeddings and it reviews
standard, widely applicable techniques like dimension reduction, as well as
applications of metric embeddings like cut problems in their various forms.
Schedule:
| Place: | TTI-C, room 230 (conference room) |
| Times: | Tuesday and Thursday 3:10 - 4:30
|
Office Hours:
| Place: | TTI-C, room 271 |
| Time: | Thursday 4:30 - 5:30
|
Homework
- Homework 1 (due Jan, 26th):
ps - pdf
- Homework 2 (due Feb, 9th):
ps - pdf
- Homework 3 (due Feb, 28th):
ps - pdf
Topics Covered and Tentative Schedule
- Preface:
ps - pdf
- January 3rd:
ps - pdf
definition of metrics, embeddings, and distortion ⋅
finding furthest
pair in l_1 via embedding ⋅
l_infty is universal ⋅
applications to cut problems
- January 5th:
ps - pdf
subset-embedding into l_infty with low number of dimensions ⋅
embeddings into l_1 and l_2 with polylogarithmic distortion ⋅
polylogarithmic approximation to sparsest cut
- January 10th:
ps - pdf
Bourgains theorem: Embedding into l_1 and l_2 with logarithmic distortion
⋅
matching lower bound via expanders
- January 12th:
ps - pdf
Embeddings into tree-distributions
- January 17th:
ps - pdf
Embeddings into tree-distributions continued
- January 19th:
ps - pdf
Embeddings into distributions over subtrees
- January 24th: no class due to the talk by Eva Tardos
- January 26th:
ps - pdf
Random graph partitions ⋅ start of measured descent
- January 31st:
ps - pdf
Measured descent continued
- February 2nd:
ps - pdf
KPR improved random graph partitions for planar graphs
- February 7th:
ps - pdf
semidefinite programs ⋅ compute optimum
embedding into l_2 ⋅
l_2^2 metrics ⋅ start of ARV
- February 9th:
ps - pdf
ARV
- February 14th:
ps - pdf
Johnson-Lindenstrauss⋅
Isometric embedding of l_2 into l_1
- February 16th:
ps - pdf
Measure-concentration
- February 21st:
ps - pdf
l^2-metrics ⋅ ARV ⋅
embedding of l_2^2 into l_1 with distortion log^{3/4}n
- February 23rd:
ps - pdf
volume respecting embeddings
- February 28th:
ps - pdf
continued
- March 2nd:
ps - pdf
continued
- March 7th: