Grupo de Trabajo "Metric Embeddings"

Sala 3, departamento de matemáticas PUC

Temas del semestre de verano 2019

1. Teorema de Bourgain + contraejemplos (2 talks). Bibliografía: capítulo 4 de Matoušek
2. Embedding de árboles (Hierarchically Separated Trees) (2+ talks). Bibliografía: https://tcsmath.github.io/online/2018/04/12/metric-approx/
3. Lema de Gordon / Gaussian width (2 talks). Bibliografía: https://cims.nyu.edu/~bandeira/TenLecturesFortyTwoProblems.pdf
4. Desaleatorización y Johnson-Lindenstrauss (1–2 talks). Bibliografía: https://epubs.siam.org/doi/abs/10.1137/1.9781611975031.87
5. Average distortion & spectral gap (1–2 talks). Bibliografía: paper de Naor
6. Si Johnson-Lindenstrauss funciona en un espacio X, entonces X es "cerca de ser Hilbert" (1 talk). Bibliografía: paper Andoni-Naor 2009

Temas para el futuro

• Expanders y embeddings. Información general de expanders: lect15-15.pdf, lect17-15.pdf
• Embedding de espacios de Wasserstein y reducciones a espacios más clásicos
• Embedding para normas de Schatten y relación con desigualdad de Khintchine

Lista de seminarios pasados y futuros

1. [Cristóbal Guzmán, 05 Nov. 2018] Concentración de la medida, teoremas de Dvoretzky y Johnson-Lindenstrauss (para las notas, escribir a C. Guzmán)
2. [Rodolfo Viera, 12 Nov. 2018] Embedding de l₂ en l₁ y pseudorandomness (parte 1) (capítulos 2.4–2.7 de Matoušek)
3. [Rodolfo Viera, 19 Nov. 2018] Embedding de l₂ en l₁ y pseudorandomness (parte 2) (capítulos 2.4–2.7 de Matoušek)
4. [Martin Rapaport, 03 Dec. 2018] Introduction to covering numbers and metric entropy (capítulo 4, notas de Vershynin)
5. [Rodolfo Viera, 12 Nov. 2018] Assouad dimension and Lipschitz extension (capítulos 3.1–3.2 de Matoušek)
6. [Rodolfo Viera, 07 Ene. 2018] Distortion versus dimension (capítulo 3.3 de Matoušek)
7. [Mircea Petrache, 14 Ene. 2018] Corrección de errores y compressed sensing (capítulo 2.8 de Matoušek)
8. [Mircea Petrache, 21 Ene. 2018] Nearest neighbors in high dimensions (capítulo 2.9 de Matoušek)

Referencias útiles

1. Metric embeddings and dimension reduction

• Notas de Matoušek, aspectos computacionales de embeddings métricos: https://kam.mff.cuni.cz/~matousek/ba-a4.pdf
• Notas de Vershynin, reducción de dimensión lineal: https://www.math.uci.edu/~rvershyn/papers/GFA-book.pdf
• Notas de Naor, embedding de espacios métricos: https://kiranvodrahalli.github.io/notes/mat529_notes.pdf

2. Graph sparsification + Kadison-Singer conjecture

• Notas de Spielman, espectros de grafos y embeddings: http://www.cs.yale.edu/homes/spielman/561/
• Notas de Tao, real stable polynomials + Kadison-Singer conjecture: https://terrytao.wordpress.com/2013/11/04/real-stable-polynomials-and-the-kadison-singer-problem/
• Notas de Brändén, interlacing polynomials: https://people.seas.harvard.edu/~salil/cs225/fall16/branden-interlacing.pdf

3. Conexiones con otras disciplinas y listas de problemas abiertos

• Wigderson: https://arxiv.org/abs/1710.09780
• Naor: https://arxiv.org/abs/1809.02376
• Matoušek-Naor: https://kam.mff.cuni.cz/~matousek/metrop.ps

4. Otros cursos y grupos de trabajo sobre "metric embeddings"

• http://www.cs.cmu.edu/~anupamg/metrics/
• http://www.cs.toronto.edu/~avner/teaching/S6-2414/index.html
• http://www.math.tamu.edu/~florent/fallschool/program.html