University of Toronto

CSC 2414H


Lecture:  Monday 1315, BA 2165  

Instructor:  Avner Magen  
Office hours:  by appointment (SF 2301B, 9468672).  
Tutor: 
Hamed Hatami 
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.
4 problem sets 12% each.
Take home exam 40%.
Scribing of lecture notes and class participation 12%.
Date  Announcement 

19/4/06  Clarification to Q2 in the exam. First, d was wrongly used twice. the comment " d(i,j) = ij" should read "the distance in P_n between i and j is ij". 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 1718 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 1315 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:0012:00. We will discuss possible change of time then: there is a conflict with a topology course of BarNatan. 