Grupo de Trabajo "Metric Embeddings"


(sala 3, departamento de matematicas PUC)


Temas del semestre de verano 2019


  1. Teorema de Bourgain + controejemplos (2 talks) Bibliography: capitulo 4 de Matousek

  2. Embedding de arboles (Hyerarchically Separated Trees) (2+ talks) Bibliography: https://tcsmath.github.io/online/2018/04/12/metric-approx/

  3. Lemma de Gordon / Gaussian width (2 talks) Bibliography: https://cims.nyu.edu/~bandeira/TenLecturesFortyTwoProblems.pdf

  4. Desaleatorisacion y Johnson-Lindenstrauss (1-2 talks) Bibliography: https://epubs.siam.org/doi/abs/10.1137/1.9781611975031.87

  5. Average distortion & spectral gap (1-2 talks) Bibliography: paper de Naor

  6. Johnson-Lindenstrauss fonciona en un espacio X, entonces X es "cerca de ser Hilbert" (1 talk) Bibliography: paper Andoni-Naor 2009

Temas para el futuro:

*) Expanders y embeddings

Información general de expanders: http://www.cs.yale.edu/homes/spielman/561/lect15-15.pdf http://www.cs.yale.edu/homes/spielman/561/lect17-15.pdf

*) Embedding de espacios de Wasserstein y reducciones a espacios mas clasicos

*) Embedding para normas de Schatten y relacion con disegualidad de Kintchine


Lista de seminarios pasados/futuros (ver links abajo para PDF's de notas):

  1. [Cristobal Guzman - 05 Nov. 2018] - Concentracion de la medida, teoremas de Dvoretzky y Johnson-Lindenstrauss (para las notas, escribir a C. Guzman )

  2. [Rodolfo Viera - 12 Nov. 2018] Embedding de l_2 en l_1 y pseudorandomness (parte 1) (capitulos 2.4-2.7 de Matousek)

  3. [Rodolfo Viera - 19 Nov. 2018] Embedding de l_2 en l_1 y pseudorandomness (parte 2) (capitulos 2.4-2.7 de Matousek)

  4. [Martin Rapaport - 03 Dec. 2018] Introduction to covering numbers and metric entropy (capitulo 4, notas de Vershynin)

  5. [Rodolfo Viera - 12 Nov. 2018] Assouad dimension and Lipschitz extension (capitulos 3.1 - 3.2 de Matousek)

  6. [Rodolfo Viera - 07 Ene. 2018] Distortion versus dimension (capitulo 3.3 de Matousek)

  7. [Mircea Petrache - 14 Ene. 2018] Correccion de erores y compressed sensing (capitulo 2.8 de Matousek)

  8. [Mircea Petrache - 21 Ene. 2018] Nearest neighbors in high dimensions (capitulo 2.9 de Matousek)

Referencias utiles:


1- metric embeddings and dimension reduction

*Notas de Matousek - aspetos computacionales de embedding metricos https://kam.mff.cuni.cz/~matousek/ba-a4.pdf

Notas de Vershynin - reduccion de dimension lineal https://www.math.uci.edu/~rvershyn/papers/GFA-book.pdf

Notas de Naor - embedding de espacios metricos 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 Branden - entrelacing polynomials https://people.seas.harvard.edu/~salil/cs225/fall16/branden-interlacing.pdf


3 - conecciones con otras disciplinas y unas listas de problemas abiertos:

Widgerson: https://arxiv.org/abs/1710.09780

Naor: https://arxiv.org/abs/1809.02376

Matousek-Naor: https://kam.mff.cuni.cz/~matousek/metrop.ps


4 - Otros cursos - grupos de trabajo sobre el tema "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