Instructor:
Mordecai Golin
golin@cs.ust.hk
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
|
Date |
Presenter |
Topic |
| 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