COMP670P -- Spring 2007

Topics in Theory: Metric Embeddings and Algorithms


Mordecai Golin


Course description:
A quick and dirty introduction to the basic concepts of embeddings followed by a survey of recent work in computer science that uses embeddings.

The course will start with the instructor giving two or three introductory lessons on the basics of  embeddings. The remainder of the course will be participants presenting papers. All participants should

A library of papers on the topic are here.
A list of  which papers have been chosen for presentation by which participants is available here.


Similar Courses:
A list of similar courses is available here

Class schedule:
Tuesday & Thursday from 2-3:20PM in room 3304






Thursday, Feb 15 Mordecai Golin  Organizational Meeting
Tuesday,  Feb 20 No class  New Year Break
Thursday, Feb 22 No class  New Year Break
Tuesday, Feb 27 No class  
Thursday, March  1 Mordecai Golin
Introductory Material:  The Johnson-Lindenstrauss Theorem

The first few sections of Chapter 15  Lectures on Discrete Geometry by Jiri Matousek.
S. Dasgupta, A. Gupta. An elementary proof of a theorem of Johnson and Lindenstrauss
D. Achlioptas. Database Friendly Random Projections, PoDS 2000.
Tuesday, March 6 Mordecai Golin

"         "

Thursday, March 8 ZHANG Qin
U. Feige.
Approximating the bandwidth via volume respecting embeddings. STOC 1998.  Presentation Slides and some notes on the paper
Tuesday, March 13 ZHANG Qin

"         "

Thursday, March 15 Iris Reinbacher
A. Gupta, A. Kumar, R. Rastogi.
Traveling with a Pez dispenser. FOCS 2001.  
Presentation Slides
Friday, March 16
Room 3464

Iris Reinbacher 
                                                       "         "
Tuesday, March 20 No class  
Thursday, March 22 Siu-Wing Cheng S. Dasgupta
Learning Mixtures of Gaussians, FOCS 1999.
Tuesday, March 27 Siu-Wing Cheng                                                      "         "
Thursday, April 12 WANG Yagjun
M. Elkin, Y. Emek, D. Spielman, and S. Teng,
Lower-Stretch Spanning Trees, STOC '05.
Presentation Slides
Tuesday, April 17 WANG Yagjun                                                      "         "
Thursday, April 19 Rajeev Raman
Bourgain's Embedding and related topics
Presentation Slides
Tuesday, April 24                                                     "         "
Thursday, April 26 Rajeev Raman
Discussed the talk A Concise Survey of Compressed Sensing by Graham Cormode from the Workshop on Algorithms for Data Streams
The Compressed Sensing Resources site has more info
Monday, May 1   No Class (public holiday)
Thursday, May 3 Iris Reinbacher
Y. Rabinovich, R. Raz.
Lower Bounds on the Distortion of Embedding Finite Metric Spaces in Graphs. D&CG 99.
Presentation Slides
Tuesday, May 8 XIA Jian
J. Fakcharoenphol, S. Rao and K. Talwar
A tight bound on approximating arbitrary metrics by tree metrics
STOC 2003.
Presentation Slides
Thursday, May 10 Sunil Arya
Locality Sensitive Hashing
P. Indyk, R. Motwani.
Approximate Nearest Neighbors: Towards Removing the Curse of Dimensionality.
STOC 1998.
See  also Sariel Har-Peled's Notes


Choosing papers:
Each student should choose two papers to present.
The papers can be chosen from the papers lists of the courses here  or can be something else that you've found that you think is appropriate.

We are maintaining  a library of papers here