Metric embeddings
Summary
The course aims to introduce the basic concepts and results on metric embeddings, or more precisely on approximate embeddings. This area has been under rapid development since the 90's and it has strong impact on algorithms for discrete optimization problems.
Content
- Metrics: l_p metrics, distortion
- Dimension reduction by random projections: Johnson-Lindenstrauss lemma
- Metrics of negative type
- Error correction and compressed sensing
- Lower bounds on distortion: Nonembeddability of expanders
- Bourgains Theorem
Learning Prerequisites
Recommended courses
- Linear algebra 1+2
- Introduction to Algorithms or Discrete Optimization
Assessment methods
Oral
Dans les plans d'études
- Semestre: Automne
- Forme de l'examen: Oral (session d'hiver)
- Matière examinée: Metric embeddings
- Cours: 2 Heure(s) hebdo x 14 semaines
- Exercices: 2 Heure(s) hebdo x 14 semaines
- Semestre: Automne
- Forme de l'examen: Oral (session d'hiver)
- Matière examinée: Metric embeddings
- Cours: 2 Heure(s) hebdo x 14 semaines
- Exercices: 2 Heure(s) hebdo x 14 semaines
- Semestre: Automne
- Forme de l'examen: Oral (session d'hiver)
- Matière examinée: Metric embeddings
- Cours: 2 Heure(s) hebdo x 14 semaines
- Exercices: 2 Heure(s) hebdo x 14 semaines
- Semestre: Automne
- Forme de l'examen: Oral (session d'hiver)
- Matière examinée: Metric embeddings
- Cours: 2 Heure(s) hebdo x 14 semaines
- Exercices: 2 Heure(s) hebdo x 14 semaines
Semaine de référence
| Lu | Ma | Me | Je | Ve | |
| 8-9 | |||||
| 9-10 | |||||
| 10-11 | |||||
| 11-12 | |||||
| 12-13 | |||||
| 13-14 | |||||
| 14-15 | |||||
| 15-16 | |||||
| 16-17 | |||||
| 17-18 | |||||
| 18-19 | |||||
| 19-20 | |||||
| 20-21 | |||||
| 21-22 |
Légendes:
Cours
Exercice, TP
Projet, autre