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
A list of which papers have been chosen for presentation by which participants is available here.
A list of similar courses is available here.
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||
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.
Friday, March 16
|Tuesday, March 20||No class|
|Thursday, March 22||Siu-Wing Cheng||
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.
|Tuesday, April 17||WANG Yagjun||" "|
|Thursday, April 19||Rajeev Raman||
Bourgain's Embedding and related topics
|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.
|Tuesday, May 8||XIA Jian||
J. Fakcharoenphol, S. Rao and K. Talwar
A tight bound on approximating arbitrary metrics by tree metrics
|Thursday, May 10||Sunil Arya||
Locality Sensitive Hashing
P. Indyk, R. Motwani.
Approximate Nearest Neighbors: Towards Removing the Curse of Dimensionality.
See also Sariel Har-Peled's Notes
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