University of Toronto
Department of Computer Science

CSC 2414H
Metric Embeddings

Spring 2006

 


Lecture: Monday 13-15, BA 2165

Instructor: Avner Magen

Office hours: by appointment (SF 2301B, 946-8672).

Tutor: Hamed Hatami

Syllabus (tentative)


  • Finite Metric spaces. l_p metrics, embeddings, distortion.

  • Embedding into l_p. Bourgain fundamental theorem. relations between l1 and l2, the cut cone, hypermetrics and negative type metrics.

  • Complexity of optimally embedding a metric space into l2, lp.

  • Metric embeddings application in Computational Geometry.

  • Dimensionality reduction: Johnson Lindensrauss Lemma; probability in high dimensional Hilbert space. (no) dimension reduction in l1.

  • Inembeddability results: Poincare inequalities; the role of expansion in embeddings; Duality theorem and complementary slackness; Markov-type; Harmonic Analysis on the hypercube.

  • Volume respecting embeddings: what extends/ what not? approximating min bandwidth.

  • Embedding into distribution of trees. A generic reduction for approximation algorithms based on embeddings.

  • Special type of graphs. Planar graph embed well in Euclidean space.

  • Cut problems, Negative Type metrics and Integrality gaps - embeddability relations. sqrt{log n} algorithm for sparsest cut (Arora, Rao, Vazirani).

  • Special metrics. Edit distance; earthmovers distance.

  • implications of ARV; measured descent.

    Reading

    The main text for the course is Matousek's text "Lectures on Discrete Geometry". The (most) relevant chapter is available online here.
    Another important book is Deza and Laurent's book "Geometry of Cuts and Metrics" which mainly focusses on isometries rather than distortion incurring embeddings.

  • Surveys:

    1. Chapter on embeddings in Handbook of Discrete and Computational Geometry, Jiri Matousek and Piotr Indyk.
          many theorems and facts (but no proofs).
    2. Survey by Piotr Indyk at FOCS 2001.
          algorithmic applications.
    3. Finite Metric Spaces - Combinatorics, Geometry and Algorithms by Nati Linial
          Proceedings of the International Congress of Mathematicians III, 573--586 Beijing, 2002.

  • Other courses on the subject are Manor Mendel's course at Hebrew University (2002) and Gupata's and Ravi's course at CMU (2003).


    Grading

    4 problem sets 12% each.

    Take home exam 40%.

    Scribing of lecture notes and class participation 12%.

    Lecture notes scribing

    Here are templates for writing scribes in latex. You will need this class file and you might want to use bib file, eps file and jpg file (the last two are definitely not a must). This is the pdf version of that file (lecture0). A first draft of the notes is expected in the following lecture.

    Assignments

    Assignment 1. New version was uploaded 26/1 10:40. see also clarifications and corrections .
    Assignment 2
    Assignment 3
    Assignment 4

    EXAM

    Lecture Notes

    Week 1: Introduction to the area of metric embedding. l_p norms, embeddability, distortion. Motivation and history. Lecture notes by Costis Georgiou.

    Week 2: Bourgain's Theorem - Every metric space on n points embeds to l_p with distortion O(log n).     Lecture notes by Periklis Papakonstantinus.

    Week 2: Toturial -- Embedding tree metrics into normed spaces.     Lecture notes by Hamed Hatami.

    Week 3+4: Embedding metrics into distribution of trees.     Lecture notes by Nilesh Bansal and Ilya Sutskever.

    Week 4: Toturial -- Background material on expander graphs and expansion properties.     Lecture notes by Hamed Hatami.

    Week 5: Johnson Lindenstrauss Dimension-reduction lemma     Lecture notes by Ilya Sutskever and Igor Naverniouk.

    Week 6: Dimension reductions that apply to angles,volumes, etc. Lower bound techniques for l2 embeddability.     Lecture notes by Costis Georgiou.

    Week 6: Toturial -- A lower bound on the distortion of an embedding the diamond graph into l_2 and into l_p.     Lecture notes by Hamed Hatami.

    Week 7: inembeddability in l2 and the structure and algorithmic role of l1 metrics.     Lecture notes by Periklis Papakonstantinus.

    Week 8: embedding to l1, sparsest cut and methods for inembeddability in l1metrics.     Lecture notes by Nilesh Bansal.

    Week 9: no dimension reduction in l1. Euclidean embeddings of planar graphs     Lecture notes by Ilya Sutskever.

    Week 10+11: ARV approximation algorithm     Lecture notes by Igor Naverniouk.

    Week 10: Toturial -- The big core theorem of Lee.     Lecture notes by Hamed Hatami.

    Week 13: new inembeddability results for $\ell_1$.     Lecture notes by Hamed Hatami.



    Announcements

    Date Announcement
    19/4/06

    Clarification to Q2 in the exam. First, d was wrongly used twice. the comment " d(i,j) = |i-j|" should read "the distance in P_n between i and j is |i-j|". When we embed into a metric d, we mean that for points i,j, the distance in the image is d(f(i),f(j)), and the mapping f has distortion <= D.

    29/3/06

    A4 is out.

    21/3/06

    Home exam: to be collected 17/4 and returned 27/4.

    20/3/06

    A3 is due Friday 24/3 to my office or mailbox.

    20/3/06

    Clarification to A3 Q3. k is the minimum eigen value of the *adjacency matrix* of G.

    11/3/06

    A3 is out.

    9/3/06

    Class next week is to be held Friday 17/3, 12:00. Location is the same - BA2165.

    27/2/06

    Remember -- tutorial today 27/2 at 5:00 in BA025.

    17/2/06

    We will have a class Monday 20/2 to compensate for the lost one last week. Same time same place.

    15/2/06

    A2 is out.

    8/2/06

    People have asked me to post the topics I will be discussing in the follwoing lecture. So on 13/2 we will finish with few more aspects of dimension reduction, and will be then talking about lower bound techinuqes for embeddings into l_2. Particulartly, we'll show hamming cube have distrotion at least \sqrt{dimension} when embedded into l2, and that expander graphs cannot be embedded with better than log n distortion. Matousek's book is a good source for these.

    6/2/06

    There will be an additional tutorial 13/2 5:00 B025. Hamed will continue the expander background discussion and talk on more selected solutions of A1.

    6/2/06

    Remember -- there is a tutorial Monday 6/2 at 5:00 in BA025. Again this is highly recommended as new material will be covered. This time the focus will be expaner graphs, and object that will play an important role in future discussion.

    26/1/06

    Corrections to A1. See above for a new version and a short description of the modifications.

    19/1/06

    Assignment 1 is out. Due next monday 29/1.

    19/1/06

    We will hold tutorials usually every other week. It will take place Monday 17-18 in BA025.

    17/1/06
    		OK, so we have a permanent place to have the course in now, BA2165. For the record, April 4 it will be in BA1230.
    15/1/06

    Notice time change. Monday 13-15 BA 1230.

    7/1/06

    Please send me an email and tell me (i) whether you think of taking the course for credit or just audit (ii) your department. (iii) Phd/Master + year of study. (iv) if you have a conflict with the current time, and when are you free on monday/friday afternoon?

    5/1/06

    First class will be on 12/1, 10:00-12:00. We will discuss possible change of time then: there is a conflict with a topology course of Bar-Natan.