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:  TTIC, room 230 (conference room) 
Times:  Tuesday and Thursday 3:10  4:30

Office Hours:
Place:  TTIC, 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
subsetembedding 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 treedistributions
 January 17th:
ps  pdf
Embeddings into treedistributions 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
JohnsonLindenstrauss⋅
Isometric embedding of l_2 into l_1
 February 16th:
ps  pdf
Measureconcentration
 February 21st:
ps  pdf
l^2metrics ⋅ 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: